## A game

Posted on: January 19th, 2014 by
2

You and your friend play the following game. Each of you secretly pick an integer between 1 and N and write it on a card. The winner is the one who picked the larger number, unless the other person is exactly 1 below the larger number in which case the smaller number wins. In case of a tie, you repeat the game.

What is the optimal strategy to win this game?

## Chess king's tour continued

Posted on: January 18th, 2014 by

This is a continuation of yesterday's puzzle. Now, the chess king pays a penalty if he makes a horizontal or vertical move. Diagonal moves are free. Find a loop for the king that visits all the squares exactly once and returns to the starting cell so as to minimize the number of horizontal or vertical moves.

## Chess King's tour

Posted on: January 16th, 2014 by

A chess king wants to visit each square on an 8x8 chessboard exactly once and finally come back to the starting square thus completing the loop. Show how he can accomplish that.

## Generating random numbers from coin flips

Posted on: January 15th, 2014 by

You have a fair coin that you can toss as many times as you like. Show how you can generate a discrete random number X that takes value 1 with probability p1, value 2 with probability p2, .... value n with probability pn (p1+p2+...pn=1).

If you have taken a class in Information theory and find the above puzzle too easy, here is a harder puzzle: Show that for any $\epsilon>0$, there exists $n$ large enough such that it is possible to generate any random variable $X$ of entropy $H(X)\le n$ with an average of $n(1+\epsilon)$ fair coin flips.

## Find the Golden year

Posted on: January 14th, 2014 by

You are given a table of names of scientists and their birth and death year, sorted alphabetically by the names of scientists. Devise an efficient algorithm to find the year when the largest number of scientists lived.

- via Algorithmic puzzles

## A geometry problem

Posted on: January 13th, 2014 by
4

Show that the distance $d$ between the circumcenter and incenter of a triangle satisfies $d^2=R(R-2r)$ where $R$ is the circumradius and $r$ is the inradius.

- via Euler

## King's reach

Posted on: January 12th, 2014 by
1

A king moves on an infinite chessboard. How many different squares are reachable by the king in n moves?

- via Algorithmic puzzles

## Sliding puzzle

Posted on: January 11th, 2014 by

Enjoy a sliding puzzle. Slide the pictures into the empty space to solve the jigsaw. The numbers 1,2,...8 at the bottom tells the location of the picture cell in the jigsaw.

## Tiling a board - generalize

Posted on: January 10th, 2014 by

Consider a $3^n\times 3^n$ board that contains $3^{2n}$ cells each of dimension 1x1.
An L-shaped tromino is a piece that is L-shaped and occupies 3 cells.
Can we tile a $3^n\times 3^n$ board using L-shaped trominoes?

- via Algorithmic puzzles

## Tiling a board

Posted on: January 9th, 2014 by