Miguel Palomino - Puzzles and mathematical recreations

Like most Science students, I find fascinating the ingenuity that lies beneath the, in many cases deceptively simple, puzzles and mathematical recreations. Here I have collected some with pointers to many more.

Short puzzles

Here are some classic problems to get your teeth into. Of course, no solutions are given! (But you can email me to check if yours are right...)

1.
Given a regular, 8x8 chess board, try to cover all of it except for the top-left and bottom-right squares, using 31 dominoes (size 2x1) that can be placed either horizontally or vertically.

2.
A file of soldiers marching in a straight line is one kilometer long. An inspecting officer starts at the rear, moves forward at constant speed until he reaches the front, then turns around and travels at the same speed until he reaches the last man in the rear. By this time, the whole column, marching at constant speed, has moved one kilometer forward. How far did the inspecting officer travel?

3.
In a certain kingdom, there are exactly 3 roads leaving out of each city. Is it possible for the kingdom to have exactly 100 roads?

4.
A six-digit lottery number is called lucky if the sum of its first three digits is the same as that of the last three. Show that the sum of all lucky numbers is divisible by 13.

5.
Mr. Smith and his wife invited four other couples for a dinner. When they arrived home, some people shook hands with some others (of course, nobody shook hands with their spouse or with the same person twice), after which Mr. Smith asked everyone how many times they had shaken hands. The answers, it turned out, were different in all cases. How many people did Mrs. Smith shake hands with?