Here are some of my favorite brain teasers.
Hints are given at the bottom of the page. Solutions - well if you solved
the problems you know you are right, otherwise you just need to think more...
None of the riddles involve "tricks", these
are pure mathematical riddles.
Hints: (Hints)
Solutions: (Solutions)
Home Page: (Home
Page)
The 100 Cables (this is a beautiful one, no knowledge of math required):
In a very tall building, 100 cables were placed connecting the roof to the basement. Unfortunately the people that placed them forgot to tag them, so nobody knows which end at the top leads to which end at the bottom. But, fortunately our engineers came up with a series of experiments that led to a solution. In each experiment they connected several (one or more) pairs of cables at the roof to batteries, so that each battery is connected to exactly 2 cables (one to the '+' and one to the '-'). They would then go down, and using a light bulb they would find pairs of cables that turn the light bulb on. They would mark their results (doesn't matter how), and then go up to make the next experiment. What is the minimum number of experiments that is required to know exactly which cable end at the roof leads to which cable end at the bottom? (Show how to do it, and prove that it is minimal).The 10 Pirates (nice but not hard, no knowledge of math required):Note: obviously the maximum number of pairs that can be connected in one experiment is 50, because each battery connects exactly 2 cable ends and there are 100 of these. Now imagine that the cables at the roof are R1, R2, ...R100, and that the cables at the basement are B1, B2, ...B100. If we connect cables (R1, R2) and (R3, R4) at the top, and then go down to the basement we find 2 pairs. Say that these are (B1, B2) and (B3, B4). Notice that in this case all the following assignments are valid: (R1->B1, R2->B2, R3->B3, R4->B4) (R1->B2, R2->B1, R3->B3, R4->B4) (R1->B3, R2->B4, R3->B1, R4->B2) and so on (5 more options).
10 pirates have found a treasure of 100 gold coins, and they wish to divide the treasure among them. The pirates have a hierarchy, and to solve the problem they came up with the following system: Let the last pirate in the hierarchy come up with a suggestion, then vote for it. If at least 50% of the votes (including his own vote) are for it, then that's the way the money will be split. Otherwise, cut off his head, throw his body to the sharks, and go to the next one in the hierarchy, and repeat the same process until a suggestion is accepted. Fortunately or Unfortunately for you, you are the last pirate in the hierarchy, and so you are required to make the first suggestion. What is the best suggestion you can make? (for a suggestion to be the best you must remain alive, and it should maximize your profit. Prove why this is the best possible suggestion for you).The Duck in the Lake (very nice and not hard, very basic geometry is needed):Note: The pirates are rational, and they all try to maximize their profits.
In the middle of a circular lake with radius R there's a duck. On the shore there's a hungry wolf, but the wolf can only run in circles around the lake (he cannot swim or go anywhere else, just stay on the circle). The speed of the wolf is four times the speed of the duck. How can the duck escape from the lake without being eaten by the hungry wolf? (The solution is the path that the duck needs to take that will let it get to the shore and not leave the wolf enough time to be waiting there for the duck).Coloring Space with 2 Colors (easy, very basic geometry is needed):Note: The wolf always moves in the shortest way to the point on the circle that is closest to the duck. Both duck and wolf can change directions at no time.
Is it possible to color the 2 dimensional space of real numbers (R x R) with only 2 colors, such that no two point that are of the same color have a distance D between them? (Show that it is not possible).Coloring Space with 3 Colors (harder, very basic geometry is needed):
Is it possible to color the 2 dimensional space of real numbers (R x R) with only 3 colors, such that no two point that are of the same color have a distance D between them? (Show that it is not possible).Points in a Rectangle (moderately hard, basic geometry is needed):
Given a 1x1 square, and 9 points in it (where no 3 points are colinear i.e. on the same line), prove that there's at least one set of 3 points that form a triangle whose area in no more than 1/8.Point Matching (hard, basic geometry is needed):
Given n blue points and n red points such that no 4 of them are colinear (i.e. no 4 points are on the same line), we pair the points in <blue, red> pairs to get n pairs, and draw a line between two points in the same pair. We call this process matching. Prove that there is a matching for which no 2 lines cross each other. There are many ways to prove this. One of these is very nice and so I wrote it down below.Almost Bipartite Graphs (3 difficulties, knowledge of basic graph algorithms and complexity is required):
An undirected Graph G=(E,V) is defined to be a Bipartite Graph iff the set of vertices V can be split in two (V1, and V2) such that all edges in E have one vertex in V1 and the other in V2.
An undirected Graph G=(E,V) is defined to be an Almost Bipartite Graph iff there is an edge e such that the graph G':=(E\{e}, V) is Bipartite. Find an algorithm that decides if a connected graph G is Almost Bipartite in O(E*E) (very easy), O(E*V) (easy), O(E+V) (hard).
Hints: (Hints)
Solutions: (Solutions)
look further down.
100 cables: One solution that many people come up with is by using 7 experiments (7= Ceil(log 100) ), but the real solution uses less than 7 experiments.
10 pirates: What happens if there are only 2 pirates?
The duck in the lake: Think about the ducks angular speed.
Coloring 2 colors: If you came here to look for a hint on this one then you don't know your basic geometry.
Coloring 3 colors: Think of how you would do it if you only had 2 colors (i.e. the previous problem). This one uses similar ideas but a more complex structure.
9 Points: How would 2 points restrict the placement of the other points if you wanted to falsify the statement?
Point Matching: No hint, see solution below.
Almost Bipartite Graph: BFS (Breadth First Search).
Solutions:
Point Matching: The matching that has the minimal total length of lines has no crossing lines (easy to show).