Expert – Page 2 – Puzzle Prime

Gods of Truth

Section: Brain Teasers Category: Deduction

Difficulty: Expert

You encounter three Gods in a room – the God of Truth, the God of Lie and the God of Uncertainty. You don’t know which one is which, but know that the God of Truth always says the truth, the God of Lie always says the lie and the God of Uncertainty sometimes lies and sometimes says the truth. You can ask in succession each of the Gods a unique question, to which they can reply only with “Yes” or “No”. However, their responses will be in their native language – “Da” or “Ne”, and you don’t know which translation to which answer corresponds. Your task is to figure out what questions to ask the Gods, so that will recognize which one of them is the God of Truth, which one is the God of Lie and which one is the God of Uncertainty.

SOLUTION

Label the gods with numbers – 1, 2, and 3.

First, ask god 1 “If I ask you whether god 2 is random, would you say ‘Da’?”. If he responds “Da”, then god 3 is not the god of uncertainty. If he responds “Ne”, then god 2 is not the god of uncertainty. In both cases we will be able to find a god which is not the god of uncertainty, let without of generality that is god 3.

Next, ask god 3 “If I ask you whether you are the God of Lie, would you say ‘Da’?”. If he says “Da”, then he is the God of Truth. If he says “No”, then he is the God of Lie.

Finally, ask god 3 whether god 1 is the God of Uncertainty and conclude the identities of all gods.

Raymond Smullyan April 19, 2022

1 Comment

Black and White

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

A boy draws 2015 unit squares on a piece of paper, all oriented the same way, possibly overlapping each other. Then the colors the resulting picture in black and white chess-wise, such that any area belonging to an even number of squares is painted white and any area belonging to an odd number of squares is painted black.

Prove that the total black area is at least one.

SOLUTION

Draw a grid in the plane which is parallel to the sides of the squares. Then, take the content of each cell of the grid and translate it (move it) to some chosen unit square. The points in that unit square which are covered by odd number of black pieces color in black, the rest color in white. It is easy to see that after doing this, the entire unit square will be colored in black (each of the 2015 squares cover it once completely). This implies that the total black area is no less than 1.

Puzzle Prime March 16, 2022

0 Comments

In the Padurea Forest

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Graph Theory

In the Padurea forest there are 100 rest stops. There are 1000 trails, each connecting a pair of rest stops. Each trail has some particular level of difficulty with no two trails having the same difficulty. An intrepid hiker, Sendeirismo has decided to spend a vacation by taking a hike consisting of 20 trails of ever increasing difficulty.
Can he be sure that it can be done?

He is free to choose the starting rest stop and the 20 trails from a sequence where the start of one trail is the end of a previous one.

SOLUTION

Place one hiker in each of the rest stops. Now, go through the trails in the forest one by one, in increasing difficulty, and every time you pick a trail, let the two hikers in its ends change places. This way the 100 hikers would traverse 2000 trails in total, and therefore one of them would traverse at least 20 trails.

Unknown Author March 13, 2022

0 Comments

FEATURED

Prisoners and Boxes

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Featured

There are 100 inmates living in solitary cells in a prison. In a room inside the prison there are 100 boxes and in each box there is a paper with some prisoner’s name (all different). One day the warden tells the prisoners that he has aligned next to the wall in a special room 100 closed boxes, each of them containing some prisoner’s name (all different). He will let every prisoner go to the room, open 50 of the boxes, then close them and leave the room the way it was, without communicating with anybody. If all prisoners find their names in the boxes they open, they will be set free, otherwise they will be executed. The prisoners are allowed to come up with a quick plan before the challenge begins. Can you find a strategy which will ensure a success rate of more than 30%?

SOLUTION

The prisoners can assign numbers to their names – 1, 2, 3, … , 100. When prisoner X enters the room, he should open first the X-th box in the line. If he sees inside prisoner’s Y name, he should open next the Y-th box in the line. If he sees in it prisoner’s Z name, he should open next the Z-th box in the line and so on.

The only way which will prevent all prisoners from finding their names is if there is a long cycle of boxes (length 51 or more), such that the first box in the cycle directs to the second box in it, the second box to the third box, the third box to the fourth box and so on.

It is not hard to compute that the probability of having a cycle of length K>50 is exactly 1/K. Then the probability for failure will be equal to the sum 1/51 + 1/52 + … + 1/100, which is very close to ln(100) – ln(50) = ln(2) ~ 69%. Therefore, this strategy ensures a success rate of more than 30%.

Unknown Author January 22, 2022

0 Comments

Trips in Bulmenia

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Graph Theory

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.

Show that you can create a trip passing through every path exactly once that ends in the city it starts from.
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.

SOLUTION

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.
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 every city. Therefore, these black paths create one or multiple disjoint loops passing through every city in Bulmenia exactly once.

Source:

IMO 2020

Unknown Author September 28, 2021

0 Comments

Self-Referential Aptitude Test

Section: Brain Teasers Category: Deduction

Difficulty: Expert

The solution to this puzzle is unique, but you don’t need this information in order to find it.

The first question whose answer is B is question:
(A) 1
(B) 2
(C) 3
(D) 4
(E) 5
The only two consecutive questions with identical answers are questions:(A) 6 and 7
(B) 7 and 8
(C) 8 and 9
(D) 9 and 10
(E) 10 and 11
The number of questions with the answer E is:
(A) 0
(B) 1
(C) 2
(D) 3
(E) 4
The number of questions with the answer A is:
(A) 4
(B) 5
(C) 6
(D) 7
(E) 8
The answer to this question is the same as the answer to question:
(A) 1
(B) 2
(C) 3
(D) 4
(E) 5
The answer to question 17 is:
(A) C
(B) D
(C) E
(D) none of the above
(E) all of the above
Alphabetically, the answer to this question and the answer to the following question are:
(A) 4 apart
(B) 3 apart
(C) 2 apart
(D) 1 apart
(E) the same
The number of questions whose answers are vowels is:
(A) 4
(B) 5
(C) 6
(D) 7
(E) 8
The next question with the same answer as this one is question:
(A) 10
(B) 11
(C) 12
(D) 13
(E) 14
The answer to question 16 is:
(A) D
(B) A
(C) E
(D) B
(E) C
The number of questions preceding this one with the answer B is:
(A) 0
(B) 1
(C) 2
(D) 3
(E) 4
The number of questions whose answer is a consonant is:
(A) an even number
(B) an odd number
(C) a perfect square
(D) a prime
(E) divisible by 5
The only odd-numbered problem with answer A is:
(A) 9
(B) 11
(C) 13
(D) 15
(E) 17
The number of questions with answer D is
(A) 6
(B) 7
(C) 8
(D) 9
(E) 10
The answer to question 12 is:
(A) A
(B) B
(C) C
(D) D
(E) E
The answer to question 10 is:
(A) D
(B) C
(C) B
(D) A
(E) E
The answer to question 6 is:
(A) C
(B) D
(C) E
(D) none of the above
(E) all of the above
The number of questions with answer A equals the number of questions with answer:
(A) B
(B) C
(C) D
(D) E
(E) none of the above
The answer to this question is:
(A) A
(B) B
(C) C
(D) D
(E) E
Standardized test is to intelligence as barometer is to:
(A) temperature (only)
(B) wind-velocity (only)
(C) latitude (only)
(D) longitude (only)
(E) temperature, wind-velocity, latitude, and longitude

Remark: The answer to question 20. is (E).

SOLUTION

The answers are:

Jim Propp September 22, 2021

0 Comments

Fish in a Pond

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Probability

There are 5 fish in a pond. What is the probability that you can split the pond into 2 halves using a diameter, so that all fish end up in one half?

SOLUTION

Let us generalize the problem to N fish in a pond. We can assume that all fish are on the boundary of the pond, which is a circle, and we need to find the probability that all of them are contained within a semi-circle.

For every fish Fᵢ, consider the semi-circle Cᵢ whose left end-point is at Fᵢ. The probability that all fish belong to Cᵢ is equal to 1/2ᴺ⁻¹. Since it is impossible to have 2 fish Fᵢ and Fⱼ, such that the semi-sircles Cᵢ and Cⱼ contain all fish, we see that the probability that all fish belong to Cᵢ for some i is equal to N/2ᴺ⁻¹.

When N = 5, we get that the answer is 5/16.

Unknown Author August 10, 2021

3 Comments

Hungry Lion

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

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.

SOLUTION

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.

Unknown Author July 10, 2021

2 Comments

Chess Peace

Section: Brain Teasers Category: Chess

Difficulty: Expert

Can you add all 16 black pieces on the board (king, queen, 2 knights, 2 bishops, 2 rooks, 8 pawns) and get a chess position, in which no piece is attacked by another?

SOLUTION

Yes, you can, as shown in the diagram below.

Unknown Author June 22, 2021

2 Comments

FEATURED

10 Dots, 10 Coins

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Featured

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

SOLUTION

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.

Source:

The Mathematical Intelligencer, 34:3 [September 2012], 11-14

Naoki Inaba April 10, 2021

2 Comments