Vectors -1, 0, 1

Consider all 1024 vectors in a 10-dimensional space with elements ±1. Show that if you change some of the elements of some of the vectors to 0, you can still choose a few vectors, such that their sum is equal to the 0-vector.

Denote the 1024 vectors with ui and their transformations with f(ui). Create a graph with 1024 nodes, labeled with ui. Then, for every node ui, create a directed edge from ui to ui-2f(ui). This is a valid construction, since the vector ui-2f(ui) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v1 ⇾ v2 ⇾ … ⇾ vk ⇾ v1.

Now, if we pick the (transformed) vectors from this cycle, their sum is the 0-vector:

f(v1) + f(v2) + … + f(vk) = (v2 – v1)/2 + (v3 – v2)/2 + … + (v1 – vk)/2 = 0.

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.

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.

Source:

Shortlist IMO 2017

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.

String of Words

There is a common 9-letter word in the English language, such that if you keep removing its letters one by one, the resulting 8 words are still valid. What is this word?

Remark: The removed letters do not need to be from the beginning or the end of the word.

The word is STARTLING -> STARTING -> STARING -> STRING -> STING -> SING -> SIN -> IN -> I.

FEATURED

Y-Town

In Y-town all crossroads are Y-shaped, and there are no dead-end roads. Is it true that if you start from any point in the city and start walking along the roads, turning alternatingly left and right at each crossroad, eventually you will arrive at the same spot?

Yes, it is true. If you start walking forward, eventually you will end up in a loop. It is easy to see that your entire path, including the starting spot, must belong to this loop. Therefore, eventually you will end up in the starting spot again.

FEATURED

Princess in a Palace

A princess is living in a palace which has 17 bedrooms, arranged in a line. There is a door between every two neighboring bedrooms and also a hallway which connects them all. Every night the princess moves through the inner doors from one bedroom to another. Every morning for 30 consecutive days you are allowed to go to the hallway and knock on one of the 17 doors. If the princess is inside, you will marry her. What would your strategy be?

You knock on doors:
2, 3,…, 15, 16, 16, 15,…, 3, 2.
This adds up to a total of 30 days exactly. If during the first 15 days you don’t find the princess, this means that every time you were knocking on an even door, she was in an odd room, and vice versa. Now it is easy to see that in the next 15 days you can’t miss her.