# Internet Problem Solving Contest

## Solution to Problem J – Just for Fun

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).

## Easy puzzles:

1. birds: puzzle, solution
2. bus: puzzle, solution
3. palindrome: puzzle, solution
4. bicycle: puzzle, solution
5. cube: puzzle, solution
6. girl1: puzzle, solution
7. girl2: puzzle, solution
8. statements: puzzle, solution
9. letters: puzzle, solution
10. century: puzzle, solution

## Hard puzzles:

1. 1000robbers: puzzle, solution
2. wires: puzzle, solution
3. chess: puzzle, solution
4. 24: puzzle, solution
5. product: puzzle, solution
6. cannibals: puzzle, solution
7. 5robbers: puzzle, solution
8. operation: puzzle, solution
9. coinseq: puzzle, solution
10. ipsc: puzzle, solution

## Easy puzzles: puzzle statements

#### birds

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


#### bus

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


#### palindrome

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


#### bicycle

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


#### cube

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)


#### girl1

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)


#### girl2

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


#### statements

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


#### letters

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


#### century

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).


## Hard puzzles: puzzle statements

#### 1000robbers

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


#### wires

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


#### chess

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


#### 24

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)


#### product

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


#### cannibals

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

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)


#### 5robbers

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)


#### operation

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


#### coinseq

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)


#### ipsc

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?

The answer for this puzzle consists of two lines, containing respectively:
- the ID of this puzzle


## Easy puzzles: solutions

#### birds

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

#### bus

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

#### palindrome

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.

#### bicycle

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.)

#### cube

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.

#### girl1

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.

#### girl2

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.

#### statements

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.

#### letters

0

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

#### century

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.

## Hard puzzles: solutions

#### 1000robbers

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.

#### wires

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.

#### chess

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).

#### 24

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

#### product

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.

#### cannibals

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.

#### 5robbers

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.

#### operation

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 ;)

#### coinseq

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 ;)

#### ipsc

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