Without any further words we give all the puzzles and our short solutions to each of them. To see the solutions, select the text in your browser (e.g. by dragging the mouse).

**birds:**puzzle, solution**bus:**puzzle, solution**palindrome:**puzzle, solution**bicycle:**puzzle, solution**cube:**puzzle, solution**girl1:**puzzle, solution**girl2:**puzzle, solution**statements:**puzzle, solution**letters:**puzzle, solution**century:**puzzle, solution

**1000robbers:**puzzle, solution**wires:**puzzle, solution**chess:**puzzle, solution**24:**puzzle, solution**product:**puzzle, solution**cannibals:**puzzle, solution**5robbers:**puzzle, solution**operation:**puzzle, solution**coinseq:**puzzle, solution**ipsc:**puzzle, solution

Puzzle ID: birds Ten birds sit on a clothes line. We shoot and kill one of them. How many birds remain on the clothes line? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - one number: the number of birds that remain on the clothes line

Puzzle ID: bus A bus was travelling with less than 100 passengers. At stop A, exactly three quarters of the passengers got off and 7 passengers got on the bus. The same thing happened at next two stops, B and C. How many people got off at the stop C? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the number of people getting off at C

Puzzle ID: palindrome Suppose we write dates in the MMDDYYYY format. In this format, the 2nd of October 2001 is a palindrome (a string equal to its reverse): 10022001. Find the previous date that yields a palindrome in this format. The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the 8-digit string

Puzzle ID: bicycle A bicycle stands on a straight road. A piece of string is attached to its rear wheel as shown in the image:

Suppose that we slowly start to pull the string to the left. What will happen to the bicycle? A) It will start moving to the left. B) It will start moving to the right. C) It will stay in the same place. Assume that the wheel of the bicycle doesn't slip on the ground (i.e. whenever the bicycle moves, the wheel has to rotate). Also assume that the bicycle stays in an upright position all the time. The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the uppercase letter corresponding to the correct answer

Puzzle ID: cube You have a cube NxNxN. How many straight cuts are necessary to cut it into N^3 cubes of size 1x1x1? You may arrange the pieces in any way you like before making each cut. a) Solve for N=3 b) Solve for N=4 The answer for this puzzle consists of three lines, containing respectively: - the ID of this puzzle - the number of cuts from part a) - the number of cuts from part b)

Puzzle ID: girl1 In a two-child family, one child is a boy. What is the probability that the other child is a girl? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the answer in the form a/b (where a,b are relatively prime)

Puzzle ID: girl2 In an unnamed overpopulated country the rulers agreed on a new law: Each woman may have as many children as she wants to, until she gives birth to a girl. After that, she may have no more children. Assume that the law will never be broken. All families will have as many children as they are (physically and legally) able to. On each birth either one boy or one girl is born with equal chances. In the current population the ratio males:females is 1:1. What will happen in the next 100 years? A) The ratio of males to females will go up B) The ratio of males to females will stay the same C) The ratio of males to females will go down The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the uppercase letter corresponding to the correct answer

Puzzle ID: statements Given is a list with 2004 statements: 1. Exactly one statement on this list is false. 2. Exactly two statements on this list are false. 3. Exactly three statements on this list are false. ... 2004. Exactly 2004 statements on this list are false. a) Determine which statements are true. b) Replace "exactly" by "at least". Again, determine which statements are true. The answer for this puzzle consists of three lines, containing respectively: - the ID of this puzzle - the encoded answer from part a) - the encoded answer from part b) How to encode the answer? If no statements are true, write the word 'NONE' (without the quotes). Otherwise take the set of true statements and write it as a set of ranges. E.g. the set {1,2,3,7,9,100,101} is encoded as 1-3,7,9,100-101

Puzzle ID: letters How many letters does the _shortest_ correct answer to this puzzle contain? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - your exact answer

Puzzle ID: century The twentieth century ended on 31. 12. 2000, which was a Sunday. Looking into the future, on which days of the week won't any century ever end? Remember that leap years are those divisible by 400 plus those divisible by 4 but not by 100. (1996 was a leap year, so was 2000, but 2100 won't be a leap year and neither will 2047.) The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the days of the week on which no century will ever end The exact form of the answer is a comma-separated list of three-letter abbreviations of the days in the order in which they appear in a week. E.g. if the answer were Monday, Tuesday and Wednesday, write the string 'Mon,Tue,Wed' (without the quotes).

Puzzle ID: 1000robbers One thousand robbers meet in their hideout and plan to divide all the loot they stole. All robbers value their life above everything. They are smart, greedy (want as much loot as possible) and bloodthirsty (given two different outcomes with the same payoff for a robber, he prefers the one where more other robbers die). They all know this information. The robbers agreed that every day they will take a vote. If at least 50% of the robbers vote to split the loot, everybody takes a fair share and leaves the hideout. Otherwise the currently youngest robber is shot. How many robbers will survive? In the last round of voting, how many of them will vote for splitting the loot? (Assume that if a robber knows that his vote doesn't matter, he votes against splitting the loot.) The answer for this puzzle consists of three lines, containing respectively: - the ID of this puzzle - the number of robbers that survive - the number of robbers that voted to split the loot in the last round

Puzzle ID: wires Imagine that you are an electrician. You are called to a very high tower, because their lifts are broken. When you arrive, you find that the lifts were sabotaged: 2005 wires were cut and now all of them hang from the top of the tower down to its bottom. (I.e. each of the wires has got one loose end near the bottom of the tower and one loose end near its top.) Before you can proceed with the repairs, you need to identify all the matching ends of the wires. For each of the bottom ends you have to know its corresponding end at the top. Your only instrument is a simple probe -- a battery and a bulb. If you attach two ends of wires to this probe, the bulb lights up if and only if the other ends of these two wires are currently conductively connected (maybe through one or more other wires). At each end of the tower you may connect and disconnect the ends of wires in an arbitrary way. Since the tower is so high, you want to minimize the number of times you have to climb up and down the staircase, regardless of how much work you have to do while you are at the top or bottom. What is the minimum number of traversals required? (Once up and down counts as 1.) The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the minimal number of traversals

Puzzle ID: chess Given is a game of chess in progress. Your task is to determine which were the last two pieces that moved before the current position was reached. The current position:

white: king on c1, rook on b1, knight on a1, pawns on b2, c2, d2 black: king on a2 The answer for this puzzle consists of four lines, containing respectively: - the ID of this puzzle - the color of the player that moved the last piece ('white' or 'black', without the quotes) - the last move made by this player before the position was reached - the last move made by the other player Enter both moves in standard chess notation. (Assume that no piece was captured in the move the other player made.) ----------------------------------------------------------------------------- Explanation of the chess notation [a subset you need to know]: A move is written as [piece][x](destination square). The piece is represented by an uppercase letter: King Queen Rook kNight Bishop If no piece is specified, the moving piece is a pawn. The optional x means the moving piece has captured an opponent's piece. A lowercase letter is used to specify the row of the destination square: Examples: - a king moves from e4 to e5: Ke5 - a knight moves from d4 to f3, taking an opponent's rook: Nxf3 - a pawn moves from g2 to g4: g4

Puzzle ID: 24 From the numbers 1, 3, 4 and 6 create an expression giving the result 24. You may use only parentheses and the operations +, -, * and /. You have to use each of the given four numbers exactly once. The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the expression (no spaces, no unnecessary parentheses)

Puzzle ID: product The sum of some (not necessarily distinct) positive integers is 34. What is the greatest possible value of their product? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - the greatest possible product

Puzzle ID: cannibals 47 people were capured by cannibals. For some obscure reason, the cannibals want to give the prisoners one last chance. They prisoners will have to stand in a line behind each other. Then the cannibals' shaman places a hat on each of the prisoners' heads. Each of these hats will be either white or black. Each prisoner can only see the colors of the hats people in front of him received. Now the shaman will ask each of the prisoners to guess the color of his hat. The first to answer is the prisoner at the end of the line (seeing all hats except for his own), then the shaman proceeds along the line. The last to answer is the prisoner at the front of the line.. If a prisoner's guess is correct, he is released immediatly, otherwise he is left to be eaten. a) Suppose that the prisoners know this procedure and that before it starts they have the time to agree on a strategy. How many of them are GUARANTEED to be saved if they find the optimal strategy? b) Solve the same task, if there are hats of 3 different colors (mauve, ochre and navy blue). The answer for this puzzle consists of three lines, containing respectively: - the ID of this puzzle - the number of saved prisoners from part a) - the number of saved prisoners from part b)

Puzzle ID: 5robbers Five robbers (Andrew, Bill, Carl, David and Wendy) want to divide loot consisting of 1000 identical diamonds. In alphabetic order they make a proposal on how to split the loot. After a proposal is announced, the robbers take a vote. If a (strict) majority agrees, the proposal is carried out and everyone goes to spend his share. If the proposal is rejected, its author is shot. All robbers value their life above everything. They are smart, greedy (want as many diamonds as possible) and bloodthirsty (given two different outcomes with the same payoff for a robber, he prefers the one where more other robbers die). They all know this information. a) How many diamonds will Andrew get, if we suppose that each proposal may only specify how many diamonds will which of the robbers get? b) How many diamonds will he get, if each proposal may also include shooting other robbers? The answer for this puzzle consists of three lines, containing respectively: - the ID of this puzzle - the number of diamonds from part a) - the number of diamonds from part b)

Puzzle ID: operation Given are the following facts: 1 + 1 = 0 2 + 2 = 0 3 + 5 = 0 6 + 8 = 3 8 + 8 = 4 9 + 7 = 1 11 + 567 = 1 How much is 680 + 369? The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - one number: the answer

Puzzle ID: coinseq Suppose we repeatedly throw a fair coin. Clearly the expected number of throws until we see a head is 2. The expected number of throws until we see two heads in a row is already 6. Suppose H denotes a head and T a tail. So e.g. HHT is a consecutive sequence of 2 heads and 1 tail. a) What is the expected number of throws we have to make until we observe the sequence HHHHHHH? b) ... the sequence HT? c) ... the sequence HHTHHHHHTHHHHHHTHHHHHTHHHH? The answer for this puzzle consists of four lines, containing respectively: - the ID of this puzzle - the exact result from part a) - the exact result from part b) - the exact result from part c)

Puzzle ID: ipsc We really admire you if you see this puzzle statement. We tried really hard to create a really challenging last hard puzzle. We succeeded. Not even the author managed to solve it. We present a somewhat simplified version. Question: Will you participate also in IPSC 2006? Think hard before you answer... your answer will be saved in our logs! ;) The answer for this puzzle consists of two lines, containing respectively: - the ID of this puzzle - your answer (one word, use lowercase letters only)

Zero, the others will fly away as soon as they hear the shot. Ever seen birds?

By solving a simple equation we get the answer: 9.

We need the closest year that yields a valid MMDD when reversed.
Clearly 2000 doesn't work, thus the last digit in D is 1. The best
choice is clearly DD=31 (and thus YYYY=13..). Now we want to maximize
the second digit of MM. It can NOT be 9, because September has only
got 30 days. Thus MM=08 and the whole date is 08311380.

At each moment, the wheel is turning around the point where it
touches the ground. From this observation it can be easily seen
that the resulting torque causes the wheel to rotate to the left.

(A common misconception when doing the physics is computing the torque with the center of the wheel as the center of rotation. Note that if this was indeed the case, by the same reasoning we could derive the following: "Tie the string at the center of the wheel, pull. The resulting torque is zero, thus the bicycle doesn't move." This is clearly wrong. If you still don't trust our solution, try an experiment. To make the bicycle go to the right, the direction in which we pull must cross the ground to the right of the bottom of the wheel.)

(A common misconception when doing the physics is computing the torque with the center of the wheel as the center of rotation. Note that if this was indeed the case, by the same reasoning we could derive the following: "Tie the string at the center of the wheel, pull. The resulting torque is zero, thus the bicycle doesn't move." This is clearly wrong. If you still don't trust our solution, try an experiment. To make the bicycle go to the right, the direction in which we pull must cross the ground to the right of the bottom of the wheel.)

In both cases 6 cuts clearly suffice. Now consider any of the small
cubes that was initially completely inside the large cube. Whatever
we do, in each cut we will only manage to create one of its faces.
Thus 6 cuts are necessary.

A classical example of conditional probability. There are 3 equally
possible families: (older boy, younger girl), (older girl, younger boy)
and (older boy, younger boy). In 2 of these cases the other child
is a girl, thus the answer is 2/3.

The ratio will stay 1:1. Consider all families that have a baby.
Approximately one half of these babies are girls, half of them
are boys. Some of these families "advance to the next round" to
have more babies. Now consider the second-born babies. Again,
the ratio of boys vs girls is 1:1... and so on.

a) The statements contradict each other, thus at most one is true.
If none of them were true, the last statement would be true -- a
contradiction. Thus exactly one is true, 2003 are false. The true
statement is #2003.

b) If statement #k is true, so are statements #1..#(k-1). Let there be exactly k true statements. The (true) statement #k says that there are at least k false statements. The (false) statement #(k+1) says that at least (k+1) statements are false. This means that there are exactly k false statements, and thus k=2004/2=1002. True statements are #1 to #1002.

b) If statement #k is true, so are statements #1..#(k-1). Let there be exactly k true statements. The (true) statement #k says that there are at least k false statements. The (false) statement #(k+1) says that at least (k+1) statements are false. This means that there are exactly k false statements, and thus k=2004/2=1002. True statements are #1 to #1002.

0

(the shortest correct answer involving some letters is probably "four")

(the shortest correct answer involving some letters is probably "four")

By using a calendar we can quite easily find that the last day of the century
repeats with a period 4. (This corresponds to 400 years. As soon as we see
that the last weekdays of 2000 and 2400 are the same, we may conclude that
the sequence is periodic, because the pattern of leap years repeats with
the same period.) The never-occuring days are Tuesday, Thursday and Saturday.

Let N be the number of robbers. If N=1, the only robber takes the loot.
If N=2, the vote of robber 2 is enough to split the loot. If N=3, robbers
1 and 2 know that IF robber 3 dies, they get 50% each (the result for N=2),
thus they won't vote for 33.3% and robber 3 dies. By extending this result
we see that the robbers agree iff their count is a power of 2. Thus there
will be 512 survivors, 256 of them will vote for splitting the loot (and
saving their necks), the others will be against it.

Label lower ends X1 to X2005. Connect: X1-X2, X3-X4, ..., X2003-X2004.

Climb up. Find the pairs, label them U1-U2, ..., U2003-U2004 (in an arbitrary way, the numbers won't match the lower ones yet). The last wire will be U2005. Connect U2-U3, U4-U5, ..., U2004-U2005.

Climb down. Disconnect everything, but keep the old marks. Relabel X2005 to L2005. Find its current pair Xn, label it L2004. Its previous pair [for the record: it is X((n-1) xor 1 + 1)] will be L2003. Continue in the same way until all wires have a L label. Now clearly for each n Ln and Un are opposite ends of the same wire.

Climb up. Find the pairs, label them U1-U2, ..., U2003-U2004 (in an arbitrary way, the numbers won't match the lower ones yet). The last wire will be U2005. Connect U2-U3, U4-U5, ..., U2004-U2005.

Climb down. Disconnect everything, but keep the old marks. Relabel X2005 to L2005. Find its current pair Xn, label it L2004. Its previous pair [for the record: it is X((n-1) xor 1 + 1)] will be L2003. Continue in the same way until all wires have a L label. Now clearly for each n Ln and Un are opposite ends of the same wire.

Black couldn't move last (the king would have to
move from check and there is no way he could get
it one move earlier). Thus the last to move was
white. White pawns didn't move, white rook couldn't.
Two last moves remain: Nb3a1 and Kd1c1.

It looks as the problem with the black king remains. The solution is simple: the moving white piece could capture a black piece that made black's last move. By trying out all possibilities we find that the only way this could happen is that the white king captured a black knight.

Thus the last move was white's Kxc1. Black's last move was Nc1 (either from d3 or e2).

It looks as the problem with the black king remains. The solution is simple: the moving white piece could capture a black piece that made black's last move. By trying out all possibilities we find that the only way this could happen is that the white king captured a black knight.

Thus the last move was white's Kxc1. Black's last move was Nc1 (either from d3 or e2).

The only solution: 24 = 6 / ( 1 - 3/4 )

Let 34 = a_1 + ... + a_k. If some a_i >= 4, we may
replace it by 2 and (a_i-2). If some a_i is 1, we may
replace a_i and a_1 by (a_i+a_1). Thus in the optimal
solution all a_i are either 2 or 3.

As 2*2*2 < 3*3, there are no more than two 2s. Thus the only optimal way is 34 = 2 + 2 + ten times 3. The product is 4*3^10 = 236196.

As 2*2*2 < 3*3, there are no more than two 2s. Thus the only optimal way is 34 = 2 + 2 + ten times 3. The product is 4*3^10 = 236196.

We can not guarantee saving the last person in the queue (the first one to answer), as
nobody sees his hat. Everyone else can be saved. Let the hat colors be 0 to K-1. Let
a_i be the number of hats of color i the last person sees. He computes the value

( \sum_{i=0}^{K-1} i.a_i ) mod K

and announces the corresponding color. Now the person N-1 computes this sum for the hats he sees. The difference is the color of his hat. He announces it and is saved. From now on all persons know his hat's color and thus they can include it in their computations. Thus everybody else computes his hat color in the same way.

Note that for K=2 this reduces to the first person announce the parity of white hats.

( \sum_{i=0}^{K-1} i.a_i ) mod K

and announces the corresponding color. Now the person N-1 computes this sum for the hats he sees. The difference is the color of his hat. He announces it and is saved. From now on all persons know his hat's color and thus they can include it in their computations. Thus everybody else computes his hat color in the same way.

Note that for K=2 this reduces to the first person announce the parity of white hats.

Using a similar way of reasoning than in the 1000robbers case we get the correct
results:

a) E alone gets everything.

Thus if there are D and E, E rejects any proposal and D is shot.

CDE: C knows that D wants to survive. Thus D will vote for any proposal. C proposes that he gets all the diamonds, this is agreed upon.

BCDE: B knows that he needs two votes to survive. If he dies, C gets 1000, D and E nothing. He has to give something to each of them, otherwise they will vote against him (due to their bloodthirst). Thus B's proposal is B 998, C 0, D 1, E 1.

ABCDE: A needs 2 votes. The cheapest way is to pay C and (D or E). Both ways leed to A getting 997 diamonds.

b) The cases E and DE remain the same.

CDE: C, knowing that D will vote for any proposal where he survives, he proposes that he (C) gets all the diamonds and (bloodthirst!) that E is shot.

BCDE: B knows that he has the vote of E that wants to survive. He needs one more, thus he has to pay D. Now he can have C shot and because of his bloodthirst he will do so. His proposal: B 999, C shot, D 1, E 0.

ABCDE: A has the vote of C, pays 1 for the vote of E. His winning proposal: A 999, B shot, C 0, D shot, E 1.

a) E alone gets everything.

Thus if there are D and E, E rejects any proposal and D is shot.

CDE: C knows that D wants to survive. Thus D will vote for any proposal. C proposes that he gets all the diamonds, this is agreed upon.

BCDE: B knows that he needs two votes to survive. If he dies, C gets 1000, D and E nothing. He has to give something to each of them, otherwise they will vote against him (due to their bloodthirst). Thus B's proposal is B 998, C 0, D 1, E 1.

ABCDE: A needs 2 votes. The cheapest way is to pay C and (D or E). Both ways leed to A getting 997 diamonds.

b) The cases E and DE remain the same.

CDE: C, knowing that D will vote for any proposal where he survives, he proposes that he (C) gets all the diamonds and (bloodthirst!) that E is shot.

BCDE: B knows that he has the vote of E that wants to survive. He needs one more, thus he has to pay D. Now he can have C shot and because of his bloodthirst he will do so. His proposal: B 999, C shot, D 1, E 0.

ABCDE: A has the vote of C, pays 1 for the vote of E. His winning proposal: A 999, B shot, C 0, D shot, E 1.

How is the result computed? Write the added numbers on a piece of paper and compute
the number of closed areas on the paper. (E.g. the number 6 creates one such area,
the number 8 is the only one to create two of them.) Yes, we know that it was
impossible to find out ;)

There is a nice connection between the number of expected throws
and the exact form of the pattern. The easiest way to find it was
to find the results for short patterns (e.g. by simulation)
and to guess how it works. We decide to omit the details ;)

We sure DO hope to see all of you next year :)