Suppose you have an infinite checkerboard where every edge is a resistance of 1 Ohm. What is the effective resistance between two adjacent vertices?
via Math overflow

## Monthly Archives for August, 2013

## Distance between dots

Suppose every point in a plane is arbitrarily colored either black or white. There is at least 1 black dot and at least 1 white dot. Show that there exists a black dot and a white dot such that the distance between the black dot and the white dot is exactly 1 unit.
- Goldman Sachs interview question for technology analyst position.

## Coin triplets

A 2 player game of successive coin tosses is as follows: First player 1 selects a triplet among the 8 triplets {HHH,HHT,HTH,... TTT} where H stands for Heads and T for tails. Player 2 then selects his triplet. After choices are made, a coin is tossed successively until one of the two triplets occurs. If player 1's triplet occurs before player 2's then player 1 …

**Continue reading the story**"Coin triplets"## Array shuffle

Suppose you have 2n elements in an array as a1,a2,...an, b1,b2,...bn. You want to reorder the elements so that the array is a1,b1,a2,b2,... an,bn. Show how to achieve this using O(log n) space and O(n) time. (It is trivial if you have O(n) space.)
SPOILER WARNING: Solution can be found in this paper.

## card shuffles

52 cards numbered 1,2,...52 are shuffled and kept face-down. Then you inspect the top card. If the top card is k, then you remove it and replace it in the k-th position in the deck. You keep repeating this procedure until there is a 1 on the top. Show that after finitely many steps there will eventually be a 1 on the top.
via Stack …

**Continue reading the story**"card shuffles"## Divide into two groups

Can you divide the numbers 1,2,3,...,15 into two groups, with group A containing 13 numbers and group B containing 2 numbers such that the sum of the numbers in group A equals the product of the numbers in group B?
- via 1999 Russian math olympiad. This problem was brought to my attention by Subhashini