IBM Research - Ponder this - puzzle solutions
Here is one of the hardest I have seen, with a surprising solution (actually I was quite sure that somebody was putting me on with something impossible):
100 Boxes with numbers inside
In a closed room there are 100 closed boxes in a line with one number inside each of them between 1 to 100 (no repetition).
The numbers inside are in random order.
There are 100 people in another room, each one is assigned with a number between 1 to 100. No two have the same number.
Each one has to go alone to the room and find a box with his number. He can open only 50 boxes and see the numbers inside. He closes each box after
opening it, and he can't mark it, move it, change the number in it, or communicate any information to the others.
The people meet before the event and devise a game plan (algorithm).
Find an algorithm which gives over 20% success. A success means that ALL people find their numbers.
For example, an algorithm where all open the same 50 boxes (say the first 50) would guarantee that 50 people find their number, but
has 0% chance that all 100 find, so it is not a solution. Other straightforward algorithms give results close to 0%.
Hint: One of the IBM problems above can help, though a solution looks impossible at first glance (and a second...; believing that a solution exists seems to be the hardest part, so I assure you about this...).
Solution: See an equivalent puzzle and a solution in http://ma.huji.ac.il/hart/puzzle/100-a.html
Another not-easy one (which I have received from Michael Rothschild from Ramot-Hashavim, Israel; the following is rephrased with an added example):
Black and white polyhedron with an inscribed sphere
An inscribed sphere (or insphere) of a polyhedron is a sphere tangent to each
of the polyhedron's faces.
A polyhedron with black and white faces is properly colored (PC), if no two
black faces have a common edge. (They may have a common corner.)
Show that a PC polyhedron with number of black faces greater
than the number of white faces does not have an inscribed sphere.
a PC white cube (6 white faces) with cut corners, black cuts (8 black faces), does not have an inscribed sphere (if the black cuts are made tangent to the inscribed sphere of the cube, at least two of them have a common edge; if symmetric, then every two black cuts that are originally with a common cube edge (which disappears) intersect in an edge, and a smaller white square, rotated in 45 degrees, is left of each white cube face);
a PC polyhedron consisting of two right square pyramids attached on their square bases (4 white and 4 black faces) has an inscribed sphere.