Puzzles.

I claim no credit for any of the below puzzles or solutions. Source: the internet.

Q: How do you divide an L-shaped tromino into four equally shaped areas?

A: Just divide it into 4 L’s.

Q: How can you plant ten trees in five rows with four trees in each row?

A: A star

Q: There are 4 chains each made of 3 rings joined together. Opening a ring costs 2 cents, closing a ring costs 3 cents. How can you join the 4 chains into a single chain for 15 cents?

A: Break all 3 rings in one chain and use them to link the other 3 chains together.

Q: You can see 4 cards. The visible faces show 3, 8, red and brown. Which cards must you turn over to test the following statement: If (material conditional) a card shows an even number on one face, then its opposite face is red?

A: The cards that could possibly violate the rule are 8 and brown.

Q: Given a candle, a book of matches, and a box of thumbtacks big enough to hold the candle, how do you fix and light the candle on a wall (a cork board)?

A: Empty the box and attach it to the wall using thumbtacks, then put the candle inside the box, then light the candle using the matches.

Q: Why are all 6-digit integers of the form abcabc (e.g 123123) divisible by 13?

A: abc x 1001 = abcabc, and 13 divides 1001.

Q: Using only a 4 minute and 7 minute hourglass how would you measure exactly 9 minutes?

A: Start 4 and 7 at same time. Flip 4 when it runs out. Flip 7 when it runs out. Flip 7 again when 4 runs out at minute 8. Then you have exactly 1 minute left in 7, running out at minute 9.

Q: There are 3 cups. Two are right-side-up and the other is upside-down. At each move you must turn over exactly 2 cups. Is it possible to turn all the cups right-side up?

A: No because each time you flip 2 cups you change the number of right-side up cups by either 0 or 2, which means you can never change the parity of either type.

Q: 2 diagonally opposite corners are removed from a standard standard 8×8 chessboard leaving 62 squares. You are given 31 dominoes, each of which covers exactly two squares on the board. Is there an arrangement of the dominoes that will exactly cover all of the squares on the board?

A: No because the mutilated chessboard has unbalanced numbers of black and white squares, and each domino must cover exactly 1 white and 1 black square.

Q: We have n identical bottles of identical pills (each bottle contains infinite pills). 1 bottle has 1.1 gram pills, all the other bottles have 1 gram pills. Given an exact measurement scale (precise to 0.1 grams) that can weigh an infinite number of objects at once, how would you find the heavy bottle? You can only make one measurement.

A: Take i pills from the ith bottle for i from 1 to n. If all pills weigh 1 gram, then the total weight should be 1+2+..n, which is n(n+1)/2. The difference between that value and the measured value multiplied by 10 is the heavy bottle.

Q: Basketball problem: You have two options 1). One successful shot at the hoop 2). AT LEAST 2 of 3 successful shots at the hoop. Let p be the probability of making a successful hit, for what value of p will you choose option 2 over 1.

A: We want 3*ppq+ppp > p where q=(1-p), so 3*pp(1-p)+ppp>p, 3pp-3ppp+ppp>p, 3pp-2ppp-p>0, p(3p-2pp-1)>0. Use the quadratic equation: (-3(+-)sqrt(9-8))/-4 = (-3(+-)1)/-4 =1 or 0.5 which means for p>0.5, option 2 is better.

Q: There’s country where each couple keeps having children until they have a girl, then they stop. What’s the expected ratio of male to female children? Assume the probability of a newborn being male is 50%.

A: Every time a new baby is born, there is a 50% chance it is male. This stays true for all newborns, so half of all newborns will be male, regardless of what scheme you use. But let’s do the infinite series as well: 50% chance of G, 25% of BG, 12.5% chance of BBG and so on. 1 girl in each scenario so the expected number of girls is 0.5*1+0.25*1+0.125*1+… Sum of geometric series where r=0.5: S=r+r^2+r^3… rS = r^2+r^3+r^4… (1-r)S = r + r^2 – r^2 + r^3 – r^3 +… = r – r^inf = r. S = r / (1-r), in this case S = 0.5/(1-0.5)=1. Expected number of boys is 0.25*1+0.125*2+0.0625*3+… Sum of arithmetico-geometric series S=0r+1r^2+2r^3+3r^4+… rS=0r^2+1r^3+2r^4+3r^5… (1-r)S=0r+1r^2-0r^2+2r^3-1r^3+3r^4-2r^4=r^2+r^3+r^4+…=r(r+r^2+r^3+…) Apply geometric sum to get (r-1)S = r(r/(1-r)) = 0.5*1 = 0.5, so S=0.5/(1-0.5)=1.

Q: You have 2 jugs of capacities a and b, and infinite water. You can 1). Fill a jug. 2). Empty a jug. 3). Pour water from X to Y until Y is full or X is empty. Show that the amount of water in either jug is always a multiple of gcd(a,b).

A: Def. We say a divides b if ak = b. Def. gcd(a,b) is the largest k such that k divides both a and b. Lemma. Any linear combination of a and b is a multiple of gcd(a,b). Proof: lc(a,b) = sa+tb. a = x gcd(a,b). b = y gcd(a,b). Substitute in: lc(a,b) = sx gcd(a,b) + ty gcd(a,b), lc(a,b) = (sx+ty) gcd(a,b) thus lc(a,b) is a multiple of gcd(a,b). Lemma. The amount of water in each jug is always a linear combination of a and b. Induction on number of steps n. Base case n = 0. Both are empty. Inductive step: Assume amount of water in each jug is a linear combination after n pourings i.e A = va+wb, B=xa+yb. Case 1: A jug is emptied. Case 2: A jug is filled. Case 3a: Water is poured from A to B and A becomes empty. Then A=0 and B=xa+yb+va+wb=(x+v)a+(y+w)b. Case 3b. Water is poured from A to B and B is filled. Then B=b and A=va+wb-(b-(xa+yb))=va+wb-b+xa+yb=(v+x)a+(w+y-1)b. Pouring from B to A is analogous.

Q: A natural number of perfect logicians (if a conclusion can be logically deduced, they will deduce it instantly) are on an island when an oracle tells them “I can see at least one person with blue eyes who is not me”. Each person 1). Does not know his own eye color and has no way of discovering it (i.e no mirrors etc). 2) Knows that everyone else is a perfect logician, and that they also know the rules. 3). Knows the eye color of everybody else on the island, but cannot communicate with others. 4). If a logician discovers his own eye color, then he will commit suicide at noon the following day for all to witness. How long does it take for the islanders to commit suicide?

A: Induct on the number of blue-eyed logicians n. Base case: n=1. As soon as he knows nobody else has blue eyes, he knows he has blue eyes, so dies the next day (day 1). Inductive step: Suppose it is true that if there are n blue-eyes islanders then they will die on the nth day. If there are n+1 blue eyed islanders, each will reason “If I am not blue-eyed, then there will only be n blue-eyed people on this island, and so they will all commit suicide n days after the oracle’s pronouncement “. When n days pass, nobody commits suicide as none of them know if they are blue eyed or not. This leaves only the possibility that they are blue eyed, so they commit suicide on the n+1th day.

Q: You have 2 eggs and a building with k floors. There is a floor F at and above from which the eggs will break when dropped, and below from which the eggs will not break. If you drop an egg and it does not break, then it is completely undamaged and can be dropped again, if it breaks it cannot be dropped again. What strategy allows you to minimize the worst case number of steps it would take to find F?

A: A drop operation is a comparison operation: whether n is less than the tested floor or not. A comparison operation splits the search space into 2 at each step,so the search process can be described as a binary decision tree, each path through the tree corresponding to at most one solution (a leaf node). Given h comparisons, the number of unique decision paths is 2^h, so given n elements, at least ceil(log2(n)) comparisons are required to assign each element a unique decision path. This is a lower bound, meaning more eggs than that are unnecessary. If fewer eggs than the lower bound are available, then we need to incorporate linear search because eventually there is a scenario where there are >2 possibilities but only one egg left, and if we skip some floors and the egg breaks, then n could be any of the floors that we skipped or the one we are on now. If we have 2 eggs, suppose the worst case is n drops, then if the first egg breaks after k drops, the second egg should get the solution in at most n-k steps. Thus the step up begins at s, then s-1… until it gets to 1, at which point it should have reached the last floor k, so we have S=s+s-1+s-2+…+1=k. 2S=s+1+(s-1)+2+(s-2)+3+…+1+s=2k=(s+1)s. ss+s-2k=0. Using the quadratic equation we get ceil((-1(+-)sqrt(8k+1))/2). Always round up because if you round down you will not have reached the last floor before doing s drops, meaning the lower bound cannot be fulfilled, whereas with rounding up you get to the last floor before reaching s drops, so the condition always holds. The related question “how many drops in the worst case for n eggs and k floors” was answered in the paper The Egg-Drop Numbers by Michael Boardman Mathematics Magazine, Vol. 77, No. 5 (Dec 2004), pp. 368-372. The paper states that there is no closed form for the partial sum of binomial coefficients so the calculation of the least number of drops necessarily requires a tedious recursive calculation (there is a O(nlog k) solution to calculate that).