Maths Puzzles

Difficulty taxonomy:

*Easy brainteaser
** Mildly difficult brainteaser
***Hard brainteaser
**** I haven't thought about this brainteaser thoroughly, but I think that the proof is hard
***** I haven't thought about this brainteaser thoroughly / I haven't found a solution yet, but I think that the proof is very hard

1-Frog and traps (***)

A frog is standing at the origin of the real line. The frog disposes of n positive integers A_1<…<A_n. At each stage, the frog decides to jump A_i units forward (i between 1 and n). Each A_i could be used only once. At the end of this process, the frog would be situated at A_1+…+A_n. You are a mean human being and will be putting n-1 traps between 1 and (A1+…+An)-1. The frog is very smart and given the positions of the traps will decide which A_i will be used at each step. Could the frog get to (A_1+…+A_n)?

2-Hell VS Heaven (*)

It's the end of time and you arrived at a crossroad one of them leading to hell and the other leading to heaven (but you don't know which is which). At the cross roads, two omniscient identical twins are standing, with one of them always saying the truth and the other one always lying. Could you find out which road leads to heaven with only one question asked to one of the brothers?
P.S: this was a brainteaser I was asked in middle school :-D

3-Liar, wicked liar and a saint(*)

You are a detective and you've got hold of three suspects in an investigation. Your sources tell you that one of them is a liar psychopath who always lies, one of them is a wicked liar who sometimes lies and sometimes says the truth, and one of them is a saint who always says the truth (but you don't know whom is whom). Given external pressure, you can only ask three yes/no questions in total to the suspects (you can decide to ask three questions to one person or spread them out. At the end you can't ask more than three questions in total). Find the wicked liar.

4-Lazy test engineer(**)

You are in a 100-story building. you have with you two glass balls. You know that if you throw the ball out of the window, it will not break if the floor number is less than X, and it will always breaks if the floor number is equal to or greater than X. Assuming that you can reuse the balls which don't break, find X in the minimum number of throws.
We can easily generalize this problem to k glass balls and n story building

5-Rivalry between two dons (**)

You are a don hosting a party. Two hours before the start of the party, Don Corleone (your biggest rival) informs you that he poisoned one of the wine bottles in your basement, and that the poison takes exactly one hour before taking effect (killing the drinker). Being busy with other things in the party, your plan is to only use 5 of your slaves to handle this problem. You will give your slaves orders, come back in an hour to give them new orders and then come back right before the start of the party to determine which bottle is the defected one. What is the maximum number of wine bottles you can have in your basement for which you are sure to find the defected bottle?

P.S: if the constraints were a bit different( if you were to spend the two hours in the basement) you could solve this problem for an arbitrary number of bottles. Just make one of your slaves to drink a sip from each bottle recording the time at which each bottle was tried. Then subtract one hour to the time the slave died to know which bottle he drank from.

6- The devil is not that powerful after all (**)

100 people are seated in a column. Devil puts a hat of either red or blue on everyone's head. Everyone can only see the hats of all the people sitting before him. Each one has to say the color of his own hat, starting from the one sitting on the last seat who can see the hats of all 99 people before him, but not his own. He would be killed if he guessed wrong. After the last one guessed, the 99th person would guess. All his information is the hats on the 98 people before him and what the last one guessed, which he can hear. He would also be killed if he guessed wrong. Each person guess in turn till the person sitting on the first seat. Each one's information is the hats of people before him and what the people after him guessed. Those 100 people can get together and devise a strategy before the Devil puts on the hats. Devil would know their strategy and try to put on the hats so he can kill as many people as possible. What's the best strategy those 100 people can come up with to minimize the total number of people being killed? Assume everyone is unselfish and works together for this common goal.

7-  Warden And Prisoners Version I (***)

A warden in a prison is so bored with his 100 prisoners that he decided to play with them a game (society/morality will be paying the expenses). He sets up a special room in the prison having two switches (each one either on off or on). Everyday, he would take one of them (randomly) to the special room. The prisoner must flip one the switches. While in the special room, the prisoner can also state that all of his other teammates have been brought to the special room at least once. If he is right, everyone will be freed. Otherwise everyone will be killed. The prisoners can sit together one afternoon to decide on a strategy before the start of the game, after which the communication between them is not possible. Can the prisoners find a strategy to set themselves free?

8-  Warden And Prisoners Version II (The solution I know requires formal maths ***

A warden in a prison gathers the top n prisoners he has and informs them about a game he is going to play with them. He will be seating the n prisoners on a round table and put on a hat on the head of each one of them. A color of a hat is one of the n colors {c_1;...;c_n} (although all the colors might not be used). No communication is allowed when on the round table. Every prisoner will secretly write down the color of the hat on his head in an envelope and give it to the warden. If one of the prisoners gets it right, everyone is freed. Otherwise, everyone is killed. The prisoners can consult with each other 5 minutes before the start of the game. Show that they can find a strategy to get freed (I am not expecting you to find the solution in 5 minutes though. take your time ;-) )

9- Warden and Prisoners Version III (***)

A warden gathers 8191 of his prisoners to make them play a game as a team:
A red or blue hat is put on the head of each one with probability of 1/2. (i.e. equal chance of being red and blue, and what's put on one person doesn't affect what are on the other people.) Each one can only see the other people's hats, but not his own. He has to guess the color of his own hat by writing down either "Red", "Blue", or "Don't know". After all three people write down their guesses, they would win if:
1. At least one of them guessed right, and
2. None of them guessed wrong.
Note: "guessed right" is defined as guessing a color that is the color of the hat. "guessed wrong" is defined as guessing a color that is NOT the color of the hat. It's neither "right" nor "wrong" if "don't know" is guessed.

The prisoners can discuss a strategy before the hats are put on their heads. After the hats are on, they can't communicate to each other including seeing other's guess. What strategy would give them the best chance of winning and what's the probability of winning under that strategy?

10- Efficient budget cuts (**)

The U.S. government received a box from its Chinese counterpart. The box weighs an integer number of kg  between 1 and 40 kg (awesome intel given by the CIA). Given recent budget cuts, the U.S. government is using a roman scale (old-style scale which can only compare between two weights) and is keen on not spending too much. What is the minimal number of weights the government needs to buy to measure the weight of the box?

P.S: At least in this case, we can cut spending efficiently.

11-Fake ball (**)

  You have 12 identically looking basket balls. One of them is unfortunately fake with its weight marginally different from the other 11. What is the minimum number of weighs you can use to determine which ball is fake using an old-style roman scale?

(****) Generalize this problem to n balls with one of them marginally different.
Generalize this problem to n balls with k of them marginally different.

12- Challenge your imagination(****)

You have one board with a rope going through its top extremities(thus the board could be hung on the wall using the rope). Three screws are put randomly on the wall. Could you hang the board in such a way that, if you take out any two screws the board will fall down, whereas if you take any screw out the board will remain hanging?

13-Working "Dans Le Noir" (**)

One of your positive hobbies is to be in the shoes of the less fortunate for two hours every week. This week, you decided to tie your eyes up. While practicing your hobby, your friend throws 100 coins on the table with exactly 30 tails and 70 heads. He asks you to separate the coins into two sets with each set having an equal number of tails. Being disciplined yourself, you decide to carry out the task "Dans Le Noir" (i.e  blindfolded). Could you?

14- Wonderland Casino (**)

In Wonderland, Casinos are willing to lose. Wonderland slot machines are a bit different from ours. It is made of square box with a light in the middle of the square. At each corner of the square, there is a slot containing a coin (either the tail or the head is facing). You can' see the facing facet of the coin. Each time you want to play, (you pay) and you can reach into the slots to flip whichever coins you want. After you make the changes, the machine will rotate very quickly and stop at a random position so that you can't tell which corners you have tempered with in the previous trial. If all coins are tails, the machine will light up and you will win the jackpot: 1000,000 Wonderland Dollar (remember, they haven't given up the gold standard yet in Wonderland. So it is really worth it if you can win the jackpot). Can you win the jackpot?

P.S: this brainteaser is very constructive with no falling from the sky tricks. Just sheer logic!

15- R^2 coloring (**)  

Can you color the plane with 3 colors (say blue, green and red) such that any two points far off by 1 must have different colors?

16- Broken ChessBoard (**)

You own a broken chess board (8X8) with the cells in opposite corners being taken out (i.e. square (1,1) and (8,8) are gone). Could you fill the chess board with domino pieces (a domino piece would cover two cells on the board)?

17-   Only fools and horses (**)

You have a horse racing track having 5 lanes and 25 horses. The horses have distinct speeds. You would like to know which are the top three horses you have. What is the minimal number of races you need to undergo to figure that out?

(*****) Generalize this problem to n horses, k lanes and finding top m horses

P.S: finding a strategy is something. Proving it is the optimal is something else.

18- More on switches (*)

You have 100 switches in a room all initially switched off.  100  drunk persons enter sequentially to the room. The first one comes in and flips all the switches. The second one, flips every other switch.The third one flips the third, sixth  etc.(all multiples of 3). And so on till the last person flip the 100th switch. which switches will be switched on at the end?

19-  Tom and Jerry (**)

Jerry is standing in the center of a circle. Tom can't get anywhere inside, but is watching closely when and where Jerry is moving to try to catch it as soon as it gets out of the circle. What is the bound that we should have on the speed ratio (of Tom's /Jerry's) such that we are sure that Jerry can get out of the the circle without being caught?

20- Nice Geometry memories(***)

Problem I: You have a triangle ABC such that the radius intermedius of the angles B and C have equal length. Show that ABC is isosceles.

Problem II& III:

P.S: Problem I and II were given to me by my maths teacher of the 10th grade. I remember spending days to try to find it in vain (I am not good in geometry anyways :P ) My uncle spent a couple of hours to find Problem I, but some days to find problem II


21- Rectangles in Rectangles(***)

We have n rectangles forming up a bigger rectangle. Each of the small rectangles has at least a side whose length is an integer. Prove that the bigger rectangle has a side whose length is an integer.

22- Better hunter than Dick Cheney (*)

You are hunting George W Bush. At time 0 was standing at the origin of the real line. He is walking with constant speed V (meters/seconds) on the line (but you don't know what is V and which side he went left or right). We know that V is an integer. You can choose to shoot on the real line once per second ( and you are a very accurate shooter). Show that you can always hunt George W Bush down.

23- Maths Competition (***)

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

24-You gotta feed the Camel (**):

In a previous life I used to live in the desert. I had a Camel which could carry 1000 bananas. For each mile walked, the Camel needed to eat one banana. I have a thousand mile journey and 3000 bananas. What is the maximum number of bananas I can deliver at the end of the journey?

25- It's not only about maths! (*)

You are in a room which has three switches. Each switch correspond to a bulb in another which you can't see. Could you find out which switch correspond to which bulb by never coming back to switches' room (i.e. once you leave the room you can never come back

26-One on Lockers(***)

There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each one can open at most n/2 lockers and, once he looks at the number, he has to close the locker. If another person wants to see the same locker, he has to open it again himself. They can't exchange information with each other. Prove that there exists a certain constant that no matter how big n is, those people can always devise a strategy so all of them can find their own numbers with probability larger than that constant.

P.S: this is surprising because if everyone picks n/2 lockers independent of other people, the probability that all of them find their own numbers is 1/2^n, which goes to 0 as n goes to infinity.

(*****) Find the optimal strategy to maximize the probability of all of them finding their own numbers

27- Another one on Lockers (*****)

There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each person will give a referee a list of n/2 lockers to open. If his number is in one of these lockers, we would say that he " got the number right". What is the optimal strategy so that everyone " got the number right"? 

28-Salaries, a social taboo (*):

Three employees are sitting next to each other. Propose an algorithm so that they can learn the average of their salaries without anyone knowing for sure the salary of the other.

29-They are guilty of stealing.. Well, we never saw them stealing it, but we saw them fighting about it(*)

10 pirates needs to split 150 gold coins among them. Their democratic system works as follows:
All pirates are ranked by their seniority. First, the most senior pirate (called "Majority leader") propose an allocation plan that states exactly how many coins  each pirate would get. The 10 pirates would vote on the plan (no filibuster) and it would pass if more than or equal to half pirates voted for it. If it passes, pirates take their coins and go home. If it fails, the one who proposed the plan (the most senior pirate in this case) would be killed, and then the second most senior pirate would take the place of "Majority leader" and propose his plan. We repeat the same process above in the order of seniority until someone's plan is passed.

Assume every pirate makes his decision based on the following priorities:
1. He doesn't want to die.
2. Given he's not going to die, he would prefer to get as many coins as possible.
3. Given he's going to get the same number of coins, he would prefer as many other pirates to die as possible.

You are the Majority Leader, what would you do?

(**) solve this problem with 200 pirates and 100 gold coins, but the question now is what would happen?

30- Cheating Husbands (*)

In a certain matriarchal town, the women all believe in an old prophecy that says there will come a time when a stranger will visit the town and announce whether any of the men folks are cheating on their wives. The stranger will simply say “yes” or “no”, without announcing the number of men implicated or their identities. If the stranger arrives and makes his announcement, the women know that they must follow a particular rule: If on any day following the stranger’s announcement a woman deduces that her husband is not faithful to her, she must kick him out into the street at 10 A.M. the next day. This action is immediately observable by every resident in the town. It is well known that each wife is already observant enough to know whether any man (except her own husband) is cheating on his wife. However, no woman can reveal that information to any other. A cheating husband is also assumed to remain silent about his infidelity.

The time comes, and a stranger arrives. He announces that there are cheating men in the town. On the morning of the 10th day following the stranger’s arrival, some unfaithful men are kicked out into the street for the first time. How many were they?

31- Eating chocolate (*)

You have a M*N chocolate tablet. We define a "move" by breaking a A*B tablet into two tablets C*D and E*F (C+E =A , D+F = B). How many moves are needed to break it into 1*1 pieces?

32-The drunk airplane passenger (*)

100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger was drunk and sate on a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat?

33-Non uniform burning stick (*):

A stick burns out in one hour from one end to the other. How do you measure 45 minutes using two such sticks? Note that sticks are made of different material and the burning speed along different sections are different so you can't use the length of the burnt section to estimate time.

34-If you are from a country where electricity is not provided 24/7, it is very natural to think about this brainteaser: (*)

There are 66 wires connecting from the top floor to the ground floor. You can see the ends of the wires but you don't know which one on the ground floor connects to which one on the top floor. You can tie the ends of several wires together and test the connections at the other end by using a bulb and battery. For example, if you first tie wires A, B, and C together at the ground floor and then go up to the top floor, you will figure out that the bulb will light if you put it between A and B, A and C, or B and C. You can do the reverse thing by tying the ends at the top floor and test on the ground. Assume you start at ground floor with none of the wire tied, what's the minimum number of trips up and down you need to make before you can figure out all the connections from the ends on the top floor to the ends on the ground floor, which is a one-to-one mapping between them?

35- Let's make a deal (Version I) (*):

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

36-Let's make a deal (Version 2) (*):

This time you are 2 players playing this game. The first player chooses a door, the second player chooses one of the two remaining doors. Then the host (who knows which door is the car's ) chooses one loosing player and tells him that his choice is wrong. If you are the remaining player, what would you do?

37- Hidden switches (*):

You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

P.S: this problem brings back some great 1st year of college memories. It was part of an exam during my first year at LLG

38-Cutting cake (*):

You have a cake in rectangular form. Someone cuts out a rectangle inside that cake in a random position. Could you split the remainder equally?

39-Playing a game with numbers(**):

Numbers between 1 and 100 are randomly put on a table from left to right (a_1,…, a_100). A game between player A and B consists of sequentially choosing one of the numbers on the side. Player A starts by choosing a_1 or a_100. If he chose a_100, player B can choose between a_1 and a_99. etc... Once the numbers are all taken we compare the sum of the number chosen by each player. Whoever has the higher sum wins. Would you want to be player A or B? Show that you can always win.

40- Strange Party (****):

You are in a strange party where everyone knows exactly 22 other person and any two who don’t know each other have exactly 6 mutual friends. How many are there in the party?

41- Number base (Requires some maths knowledge ***)

You’ve got 1000,000 doors numbered from one to 1000,000. You can choose n numbers such that you would like to form any door number using these numbers (for example if I take all power of twos up to 19 I would be a able to form any number between 1 and 1000,000). I am a mean person who, after you choosing your n numbers, will take one out. What is the minimal n such that you can still get any number between 1 and 1000,000 regardless of the number I take?

42- Color segregation (***)

You’ve got 2*n numbers in the plane A1,…,An and B1,…,Bn such that no three points are aligned. Show that there is a permuatation sigma such that the segments [A1 B(sigma(1)]…[An B(sigma(n))] are pairwise disjoint.