Puzzles

This is a collection of some nice puzzles that I have come across.

1. Finding the connection (Source: Arun Natarajan)

There are ten wires that run underground across a river. Thus on each of the banks, there are ten ends of the wires. Unfortunately, given an end of a wire on this bank, one doesn't know which end on the other bank it corresponds to. Suppose that you an ohmmeter and a bunch of wires. (You can then, for example, connect two ends on side A of the river, and go to the side B and measure the resistance between every pair of ends to figure out which pair on side B corresponds to the pair that is connected on side A). What is the minimum number of crossings you need to make in order to figure out the matching ends of all the ten wires?

2. Randomizing the guess (Source: Todor Tsankov)

From a random distribution on the plane a point (x,y) is chosen. It is know that x and y are not equal almost always (in other words, probability that x=y is zero). You are then given one of these two numbers randomly. You have to guess whether the number given to you is the smaller or the bigger of the two. Come up with a strategy which gives the right answer with probability (strictly) more than half. Your strategy should work irrespective of the distribution.

Note that if for example you toss a fair coin and say whether the given number is bigger or smaller than the other, then the probability that your answer is correct is exactly half.

3. Knowing the scores (Source: Brian Schroeder)

A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not gauranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if *everyone* guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability that they all will pass is more than a positive constant independent of n.

4. Tangents to a curve (Source: Alexandru Oancea)

In each of the three following figures, there is a smooth curve C and two directed straight lines A and B. In each of these three cases, is it possible to smoothly translate the line A to B (with directions appropriate) so that the line is never tangent to the given curve C?

5. Clubs vs. People (Source: Amit Deshpande)

In a town, every club has an odd number of membership and every pair of clubs has an even number of common membership. Show that the number of clubs is less than the number of people.

6. Covering a polytope (Source: Amit Deshpande)

Consider a polytope in R^n whose vertices lie on the unit sphere. Show that the spheres whose diameters are the line segments connecting the vertices and the origin, cover the entire polytope. For example, in dimension 2 and in case of a triangle, this reduces to saying that if O is the circumcenter of a triangle ABC, then the circles with diameters OA, OB and OC cover the entire triangle.

7. Spanning the whole space (Source: Abhishek Tiwari)

The space R^n (n copies of the reals) has 2^n octants. If we are given 2^n vectors belonging to the interior of distinct octants, show that they will span the whole of R^n.

8. Getting out of the hell (Source: Amrit Pratap)

Three people A,B and C are locked up in three different cells in the hell. God gives them an opportunity to get out of hell. He calls these three one by one in a random order and shows them a switch. This switch is off to start with (though this information is immaterial). They are allowed to operate the switch from off to on or from on to off, or do nothing. If they can say correctly that all the three people have seen the switch at least once then they are free to go. Given that God calls each of them infinitely many times, find a strategy for all the three of them to get out. As an example, God can call the people in the following order: ABCABCABCABC... Obviously, your strategy should work no matter what the order of calling is.

9. Averaging out

An n by n square grid is filled with real numbers such that the number on each square is the average of the numbers in the neighbouring squares (two squares are neighbours if they share at least one common vertex). Show that all the numbers are the same.

10. Operating the patients (Source: Hoan Dang)

There are n doctors and m patients and each doctor needs to operate each patient. And to operate a patient the doctor has to wear gloves. What is the minimum number of gloves required so that no two people touch the same side of the gloves? You can start with the simplest case where n=m=2 and the answer in this case is "two".

11. What is the colour of my hat? (Source: Ruxandra Paun)

There are hundred people standing in a line, each wearing a blue or a red cap. Each of them can see the colour of the hat that the people in front of him/her are wearing. They are supposed to guess the colour of their hat and if they guess it wrong then they are dead! Obviously, they cannot pass any information among themselves, but they can always have a strategy decided before hand. The question is - how many people can be saved?

12. Trip efficiency (Source: Mithun G N)

Two cities A and B are 100 miles apart. A person has to travel from one city to the other in his old old car, which can travel only 50 miles with its tank full. Unfortunately, there are no gas stations between the cities. (Of course it is dumb, but still) suppose that the person cannot carry any extra gas in his car. What is the minimum number of refuellings at A does he need to do in order to reach B? (The whole point is that he can store fuel in between A and B and the problem is to figure out a clever way of doing it).

13. Was my friend lucky? (Source: Surjeet Rajendran)

There was this crazy lottery in which it is ensured that at least 90% of the participants win a prize. The way this is played is as follows:
k participants enter a room wherein the conductor of the lottery throws die. If the outcome is 6 and 6 then all these participants in the room win a prize and the lottery ends, and otherwise next set of participants are allowed to come into the room after vacating the room. Note that the number of participants inside the room, that is k, is a variable.

The way they ensure that at least 90% of the participants win a prize is setting k = 1,9,90,900,... (Convince yourself that this works).

One day, you see in the newspaper a list of names, with "90% of these people won a prize in a lottery" written underneath. Your friend's name is in that list. Assuming that you don't know anything about the lottery, what is the probability that your friend won a prize? What if you already know that this lottery is the one described above?

14. Passing on the information (Source: Amrit Pratap)

Two persons A and B are given the following task:
From a pack of (52) playing cards A should take 5 cards randomly (without replacement). He then should pass four cards to B, one by one. B should then be able to tell what the fifth card is.

What protocol can A and B use? Can you generalize this?

15. Filling water (Source: Abhishek Tiwari)

You have a glass cube with a hole at the center of a face. How can you fill the cube with water occupying one third of its volume? (there is no scale provided).

16. Slow racing

Once upon a time, there lived a king who had two sons. These two sons were not only twins by birth, but also equal in all aspects. When it was time to decide the successor, the king called his two sons and assigned them a task. The task was to take their horses to a place nearby and bring it back. The person whose horse comes the last will become the successor.

With this task in hand, the two sons set out, obviously, as slow as possible. Days pass by, and the sons don't move more than couple of meters per day! None of the two wants to loose, but certainly they want to be done with this contest. On one fine day, an old man meets these two, on his way to the capital. Hearing about the "race", he gives them an advice. At once, the two sons run to the horses and start riding them as fast as possible. The result of the race and the remaining story is irrelevant.

The obvious question : What was the suggestion by the old man?

17. Heaven or Hell

As usual, a dead man has the task of finding his way to heaven. There are three doors A,B and C in front of him, two of which lead to hell and the other to the heaven. God asks him to choose a door to enter and he chooses door A. Then the God, who always speaks the truth, tells the dead man that the door C leads to hell. He is then asked if he wants to change his mind. What should he do?

18. Sharing the loot

There are five looters who loot 100 gold coins. After looting they decide to split up and they get into a controversy regarding the share of the loot each person gets. They decide to do the following:

A lottery will be held to number each of them from one to five. Then the first person will come up with a sharing formula and there will be a voting on it. If there are at least half the people (three in this case) who agree with the sharing system, then they share according to it. Otherwise, they kill the first person and the second person will come up with another system of sharing the loot among 4 people. This continues until they share the loot.

What should the first person's sharing system be?

Back to Math page