Brain Teasers 25 - Puzzle Prime

Crashing Light Bulbs

Section: Brain Teasers Category: Insight

Difficulty: Hard

You are living in a 100-floor apartment block. You know that there is one floor in the block, such that if you drop a light bulb from there or anywhere higher, it will crash upon hitting the ground. If you drop a light bulb from any floor underneath it however, the light bulb will remain intact. If you have two light bulbs at your disposal, how many drop attempts do you need such that you can surely find which the floor in question is?

SOLUTION

The answer is 14 drops. You can do this by throwing the first bulb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 (notice that the difference decreases always by 1) until it crashes and then start throwing the second bulb from the floors in between. For example, if the first bulb crashes at floor 69, you start throwing the second bulb from floors 61, 62, 63, etc. This way the total number of throws would be always at most 14.

Proving that 14 is optimal is done using the same logic. In order to use at most 13 throws, the first throw should be made from floor 13 or lower. The second throw should be made from floor 13+12 or lower, the third throw should be made from floor 13+12+11 or lower, etc. Continuing with the same argument, we conclude that the 13th drop should be made from floor 13+12+…+2+1=91 or lower. However, if the first light bulb does not crash after the last throw, you will not be able to find out which number among 92-100 is X.

Unknown Author March 7, 2021

8 Comments

9 balls, 1 defective

Section: Brain Teasers Category: Insight

Difficulty: Advanced Tags: Weighings

You have 9 balls, 8 of which have the same weight. The remaining one is defective and heavier than the rest. You can use a balance scale to compare weights in order to find which is the defective ball. How many measurements do you need so that you will be surely able to do it? What if you have 2000 balls?

SOLUTION

First, we put 3 balls on the left side and 3 balls on the right side of the balance scale. If the scale tips to one side, then the defective ball is there. If not, the defective ball is among the remaining 3 balls. Once left with 3 balls only, we put one on each side of the scale. If the scale tips to one side, the defective ball is there. If not, the defective ball is the last remaining one. Clearly we can not find the defective ball with just one measurement, so the answer is 2.

If you had 2000 balls, then you would need 7 measurements. In general, if you have N balls, you would need to make at least log₃(N) tests to find the defective ball. The strategy is the same: keep splitting the group of remaining balls into 3 (as) equal (as possible) subgroups, discarding 2 of these subgroups after a measurement. To see that you need no less than log₃(N) tries, notice that initially there are N possibilities for the defective ball and every measurement can yield 3 outcomes. If every time you get the worst outcome, you will make at least log₃(N) tries.

Unknown Author March 1, 2021

2 Comments

Coins on a Chessboard

Section: Brain Teasers Category: Mathematics

Difficulty: Hard

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?

SOLUTION

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.

Unknown Author February 27, 2021

4 Comments

Drown or Burn

Section: Brain Teasers Category: Insight

Difficulty: Advanced

The ship you are traveling on crashes and you somehow succeed to reach the shores of an island. On this island however, a cruel tribe resides and decides to murder you. The tribals can not agree on how to do this, so they decide that if the first sentence you say is a lie, they will drown you, and if it is a truth, they will burn you. Luckily, you hear their conversation and come up with a plan. What do you tell them?

SOLUTION

You can tell them “You will drown me”. This will result in a paradox – if your sentence is true, then they will drown you, but on the other hand will be forced to burn you, which is a contradiction. Similarly if your sentence if false. Therefore they will not have a choice except to give up on their plan.

Unknown Author February 9, 2021

0 Comments

The Majority Name

Section: Brain Teasers Category: Mathematics

Difficulty: Hard Tags: Algorithm

In a long list of names, one of the names appears more than half of the time. You will be read the names one at a time, without knowing how many they are, and without being able to write them down. If you have a very weak memory, how can you figure out which is the majority name?

SOLUTION

Remember the first name and then keep track of whether it has been repeated more than half of the time. To do that, simply add 1 if you hear the name or subtract one when you hear another name. If the list finishes and your counter is positive, then the first name is the majority. If your counter drops to 0, simply restart the procedure with the next name you hear.

This algorithm, invented by R. Boyer and J. Moore, works, because if the counter ends up at 0, then each of the names up to that moment has been read at most half of the time. Therefore, the majority name appears more than half of the time in the remainder of the list.

Unknown Author February 6, 2021

1 Comment

Under a Microscope

Section: Brain Teasers Category: Science

Difficulty: Easy

How much will a 12° angle measure when looked at under a microscope that magnifies 8 times?

SOLUTION

The angle will measure the same, 12°.

Unknown Author February 3, 2021

0 Comments

Ambiguous Clock

Section: Brain Teasers Category: Mathematics

Difficulty: Hard

The hands of my alarm clock are indistinguishable. How many times throughout the day their positioning is such that one cannot figure out which is the hour hand, and which is the minute hand?

Remark: AM-PM is not important.

SOLUTION

Imagine that you have a third hand which moves 12 times as fast as the minute hand. Then, at any time, if the hour hand moves to the location of the minute hand, the minute hand will move to the location of the imaginary hand. Therefore, our task is to find the number of times during the day when the hour hand and the imaginary hand are on top of each other, and the minute hand is not.

Since the imaginary hand moves 144 times faster than the hour hand, the two hands are on top of each other exactly 143 times between 12AM and 12PM. Out of these 143 times, 11 times all three arrows are on top of each other. Therefore, we have 2 × (143 – 11) = 264 times when we cannot figure out the exact time during the entire 24-hour cycle.

Unknown Author January 27, 2021

1 Comment

Vectors -1, 0, 1

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

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.

SOLUTION

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

v₁ ⇾ v₂ ⇾ … ⇾ v_k ⇾ v₁.

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

f(v₁) + f(v₂) + … + f(v_k) = (v₂ – v₁)/2 + (v₃ – v₂)/2 + … + (v₁ – v_k)/2 = 0.

Unknown Author January 18, 2021

0 Comments

Creepy Beasts Inc.

Section: Brain Teasers Category: Deduction

Difficulty: Easy

At Creepy Beasts Inc., three of the most dreaded animals, a tiger, a wolf, and a bear, sat in their boardroom in silence while they awaited their boss. Then, Mr. Tiger broke the silence.

“Isn’t it odd that our three surnames are the same as our three species, yet none of our surnames matches our own species?”

The wolf replied, “Yeah, but does anyone care?”

They sat in silence again…

Can you figure out the surname of each animal?

SOLUTION

Since the wolf replied to Mr. Tiger, his surname can be neither Tiger nor Wolf. Therefore, the wolf’s surname is Mr. Bear. Subsequently, Mr. Tiger must be a bear, and finally, Mr. Wolf must be a tiger.

Unknown Author January 9, 2021

2 Comments

Odd Rectangle

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

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.

SOLUTION

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

Unknown Author January 6, 2021

0 Comments