Trips in Bulmenia

In the country of Bulmenia there are 40 big cities. Each of them is connected with 4 other big cities via paths, and you can get from any city to any other via these paths.

  1. Show that you can create a trip passing through every path exactly once that ends in the city it starts from.
  2. Show that you can create one or multiple trips, such that every trip passes through different cities, ends in the city it starts from, and also every city is part of exactly one trip.

Remark: The paths can intersect each other, but you cannot switch from one path to another midway.

Source: IMO 2020

  1. Let us call a trip that ends in the city it starts from a “loop”. Start from any city and keep traveling without using any path twice. If at some point you can’t continue, stop, creating a loop, and modify your trip as follows. Pick any city you have visited from which there are unused paths going out, and once again start traveling along the unused paths until you can’t continue further. Add the newly formed loop to the original trip and continue this procedure until there are no unused paths left, thus completing a loop passing through every path exactly once. This method works because there is an even number of paths going out from every city and you can get from any city to any other.
  2. Use the loop from 1. and color every second path on it in black. Then, notice that there are 2 black paths going out from evey city. Therefore, these black paths create one or multiple disjoint loops passing through every city in Bulmenia exactly once.

Hungry Lion

A hungry lion runs inside a circus arena which is a circle of radius 10 meters. Running in broken lines (i.e. along a piecewise linear trajectory), the lion covers 30 kilometers. Prove that the sum of all turning angles is at least 2998 radians.

Imagine the lion is static, facing North, and instead, the center of the arena moves around. Then, each time the lion runs X meters in some direction, this translates into the center moving X meters South. Each time the lion makes a turn of Y radians, this translates into the center moving along an arc of Y radians.

Thus, the problem translates to a point inside the arena alternating between traveling straight South and then moving along arcs around the center of the arena. Since the total distance traveled straight South by the point is 30KM and the distance between the starting and the ending points is at most 20M, the total distance traveled North must be at least 30KM – 20M = 29980M. Therefore, the total length of the arcs traversed by the point is at least 29980M, and since the radius of each arc is at most 10M, the total angle of the arcs must be at least 2998 radians. The sum of all turning angles of the lion is the same, so this concludes the proof.

Discuss this puzzle in the forum.

10 Dots, 10 Coins

If you have 10 dots on the ground, can you always cover them with 10 pennies without the coins overlapping?

Assume the dots lie in a plane and the radius of a penny is 1. Make an infinite grid of circles with radii 1, as shown on the picture, and place it randomly in the plane.

If we choose any point in the plane, the probability that it will end up inside some circle of the grid is equal to S(C)/S(H), where S(C) is the area of a coin and S(H) is the area of a regular hexagon circumscribed around it. A simple calculation shows that this ratio is larger than 90%. Therefore, the probability that some chosen point in the plane will not end up inside any circle is less than 10%. If we have 10 points, the probability that neither of them will end up inside a circle is less than 100%. Therefore, we can place the grid in the plane in such a way that every dot ends up in some circle. Now, just place the given coins where these circles are.

Married Couples

In a small village, there are 100 married couples living. Everyone in the village lives by the following two rules:

  1. If a husband cheats on his wife and she figures it out, the husband gets immediately killed.
  2. The wives gossip about all the infidelities in town, with the only exception that no woman is told whether her husband has cheated on her.

One day a traveler comes to the village and finds out that every man has cheated at least once on his wife. When he leaves, without being specific, he announces in front of everybody that at least one infidelity has occurred. What will happen in the next 100 days in the village?

Let us first see what will happen if there are N married couples in the village and K husbands have cheated, where K=1 or 2.

If K = 1, then on the first day the cheating husband would get killed and nobody else will die. If K = 2, then on the first day nobody will get killed. During the second day, however, both women would think like this: “If my husband didn’t cheat on me, then the other woman would have immediately realized that she is being cheated on and would have killed her husband on the first day. This did not happen and therefore my husband has cheated on me.”. Then both men will get killed on the second day.

Now assume that if there are N couples on the island and K husbands have cheated, then all K cheaters will get killed on day K. Let us examine what will happen if there are N + 1 couples on the island and L husbands have cheated.

Every woman would think like this: “If I assume that my husband didn’t cheat on me, then the behavior of the remaining N couples will not be influenced by my family’s presence on the island.”. Therefore she has to wait and see when and how many men will get killed in the village. After L days pass however and nobody gets killed, every woman who has been cheated on will realize that her assumption is wrong and will kill her husband on the next day. Therefore if there are N + 1 couples on the island, again all L cheating husbands will get killed on day L.

Applying this inductive logic consecutively for 3 couples, 4 couples, 5 couples, etc., we see that when there are 100 married couples on the island, all men will get killed on day 100.

Coins on a Chessboard

There is a room with a chessboard inside. On each of its 64 squares, there is placed a coin, either heads up or heads down. You enter the room and a person inside points towards one special square on the chessboard and gives you the chance to flip one of the coins (whichever you choose). Then you leave the room, your friend enters and has to guess which was the special square on the chessboard. If you two could devise a plan before entering the room, how would you make sure your friend always guesses correctly which is the special square?

First, you must enumerate the coins with numbers from 1 to 64, locate the mystery coin, and calculate the binary representation of its number, padded with zeros on the left to 6 digits length. For example, if the mystery coin is the 5th one on the 4th row, its number would be 29 and will have a binary representation 011101. Then, consider the following sets of coins:

A1 = {row 1, row 2, row 3, row 4}
A2 = {row 1, row 2, row 5, row 6}
A3 = {row 1, row 3, row 5, row 7}
A4 = {column 1, column 2, column 3, column 4}
A5 = {column 1, column 2, column 5, column 6}
A6 = {column 1, column 3, column 5, column 7}

Now, the strategy is to flip the coin which makes the parity of heads in set Ai odd if and only if the i-th digit in the binary representation of the mystery coin is 1. It is easy to check that this is always a possible thing to do.

Odd Rectangle

The sides of a rectangle have lengths which are odd numbers. The rectangle is split into smaller rectangles with sides which have integer lengths. Show that there is a small rectangle, such that all distances between its sides and the sides of the large rectangle have the same parity, i.e. they are all even or they are all odd.

Source: Shortlist IMO 2017

Split the large rectangle into small 1×1 squares and color it in black and white, chessboard-style, such that the four corner squares are black. Since the large rectangle has more black squares than white squares, one of the smaller rectangles also must have more black squares than white squares. Therefore, the four corners of that smaller rectangle are all black. Then, it is easy to see that all distances between its sides and the sides of the large rectangle have the same parity.

Puzzle at the End of the Book

“Puzzle at the End of the Book” is a very challenging puzzle from the 2017 MIT mystery hunt. The answer to this puzzle is a 6-letter word, related to a woman’s beauty. The solution is intricate and requires careful analysis of the book, some geeky references, and possibly a good amount of Google searching. Use the hints below if you need help with solving puzzle.

Source: MIT

Pay attention to the words in green. They form a riddle which needs to be answered.

Pay attention to the broken lines along the bubble speeches. Use an appropriate code to decode them.

Pay attention to the ship, the brick wall, the ladder, and the bucket. Use an appropriate code to decode them.

Pay attention to Grover’s arms. Use an appropriate code to decode them.

Pay attention to the fonts used for typing the words in red. Use their first letters to form a word.

Pay attention to the unusual words appearing in the text. Use parts of these words, combined with immediately preceding/succeeding parts of neighboring words, to get the names of six Pokemons. Use their first letters to form a word.

The names of the six muppets have the same lengths as the six words discovered from the previous steps. See which letters overlap when you compare each muppet name with its corresponding word. Arrange these letters to get the final answer.

The answer to this puzzle is MAKEUP.

In order to get to it, first you must find 6 secret fantasy related words.

1. The green words on the pages of the book form the sentence Wooden ship turned around before understanding sea monster (SIX). “Wooden ship” = ARK, “turned around” -> KRA, “understanding” = KEN, so we get KRAKEN, which is a sea monster with six letters.

2. The broken lines along the speech bubbles can be decoded using Morse code to spell Lilith, Morrigan, Scarlet, or Queen of Pain. These female demons give the secret word SUCCUBUS.

3. The ship, the brick wall, the ladder, and the bucket contain four hidden Brail letters, which spell out the word HUMA.

4. Grover’s arms encode through semaphore the Inuit mythological creature QALUPALIK.

5. The word “Puzzle” is written in five different fonts – Times New Roman, Impact, Twentieth Century, Arial, Nosifer. The first letters of these fonts form the word TITAN.

6. Each page from 2 to 8 contains some unusual words. Part of these words, combined with immediately preceding/succeeding parts of neighboring ones, give the six Pokemons Sandshrew, Pinsir, Ekans, Clefairy, Tentacruel, Eevee, Rapidash. Their first letters form the secret word SPECTER.

The names of the six muppets on the last page are Barkley, Donmusic, Elmo, Kermit, Misspigy, Oscar. They perfectly match in terms of length with the six secret words which we found above. Also, each pair of name with secret word overlap in just one position, the six resulting letters are E, U, M, K, P, A. If we arrange these letters with respect to the length of their corresponding words, we get the final answer MAKEUP.