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)?
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?
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.
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.
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.
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.
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?
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 ;-) )
A warden gathers 8191 of his prisoners to make them play a game as a team: 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?
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.
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.
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?
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?
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!
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?
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)?
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.
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?
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: http://thinkzone.wlonk.com/MathFun/Triangle.htm 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
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.
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.
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.
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?
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
There are P.S: this is surprising because if everyone picks (*****) Find the optimal strategy to maximize the probability of all of them finding their own numbers
There are
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.
10 pirates needs to split 150 gold coins among
them. Their democratic system works as follows: Assume every pirate makes his decision based on the following
priorities: 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?
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.
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?
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?
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.
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?
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?
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?
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
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?
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.
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?
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?
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. |