1617-257/Riddle Repository

From Drorbn
Jump to: navigation, search

Riddle Repository

A collection of the riddles posed at the beginning of each lecture
Date of Lecture Riddle Solutions, Discussion, etc...
Sept 12 We want to compute (x^x)'.

Prof. A claims (x^n)'=nx^{n-1}, so (x^x)' = xx^{x-1} = x^x

Prof. B claims  (a^x)' = a^x\log(a), so (x^x)' = x^x\log(x)

Smart student says (x^x)' =  x^x + x^x\log(x). Why is the derivative the sum of the Prof's solutions?

Sept 14 Can all of \mathbb{R}^2 be covered by a set of disjoint, non-degenerate, circles? What about \mathbb{R}^3? \mathbb{R}^4?
Sept 16 Can you find uncountably many disjoint subsets of \mathbb{R}?
Sept 19 Can uncountably many Y shapes be fit into \mathbb{R}^2?
Sept 21 On any pair of potatoes, can you draw a pair of 3D congruent curves? Hint (Hover) For each potato P, consider its boundary, \partial P, which will be a 2-manifold. By poking one of our potatoes with the other and allowing the potatoes to pass through each other, the intersection of the boundaries will be a 1-manifold, which will be a closed curve in 3-space.
Sept 23 Can you find uncountably many subsets of \mathbb{N} s.t. the intersection of any two of them is finite?
Sept 26 In how many ways can you place 4 different points in the Euclidean plane, such that there are 2 different distances between all the points?
Sept 28 Can you find uncountably many subsets of \mathbb{N} s.t. for any two of them A and B, (A \subset B) or (B \subset A)?
Sept 30 In a random 13-element subset of 1,2,...,52, what is the average value of the smallest element? (Credit: Yujia Yin)
Oct 3 A spherical loaf of bread is put in a bread cutting machine. Which slice gets the most crust? None of them. They all get the same amount. This was proved in class during the change of variables unit.
Oct 5 Can you write the function f(x, y) = 1 + xy + x^2y^2 as f(x, y) =\sum_{k=1}^{2}g_k(x) h_k(y)? (Credit: Yujia Yin) Yujia: This question is fairly funny if you have the right idea. Let's say you can find such g_k and h_k,where k=1,2. Then sub y=0,1,-1, you see x^2+x+1,x^2-x+1 and 1 can be written as linear combinations of g_k. But simple calculation shows these 3 polynomials are linearly independent over R,so they cannot be in the span of only two functions.
Oct 7 Prove: If you tile a rectangle (whose sides are not integers) with rectangles, at least one of those will have both sides non-integer.
Oct 10 (Thanksgiving holiday - University closed)
Oct 12 Players A and B alternate placing 1 x 2, 1 x 3, and 1 x 4 lego pieces (as they choose) on a 19 x 21 board, with no layering and no overlaps. If you cannot place a piece, you lose. Who would you rather be A or B? What if the overall size was 20 x 20?
Oct 14 No riddle. Discusses past riddle from Sept 19. No solution.
Oct 17 An ant walks at 1cm/sec along a super-rubber-band that stretches at 1m/sec. Will it ever reach the other end? Why not? How long will it take? (Credit: Kodiak Jackson) The stretching of the rubber band does not affect the ant's fractional progress, which is proportional to the ant's speed over the band's length, as it moves the ant along. Since the ant's fractional progress is inversely proportional to time and \int_1^\infty\frac{dx}{x} diverges, the ant always makes it to the end of the band.
Oct 19 How far can you go with n Jenga blocks?
Oct 21 Can you place 6 identical real-life Jenga blocks/chalks such that any two of the will touch each other?
Oct 24 Can you pack 125 1 x 2 x 4 boxes inside a 10 x 10 x 10 cube?
Oct 26 Can you pack 21 3 x 1 rectangles on an 8 x 8 board? Any constraints on where the missing piece would be?
Oct 28 No riddle. No solution.
Oct 31 A total of k kids share a loot of n indivisible candies. The first proposes a split. If not accepted by a strict majority, she leaves and the second proposes a split... etc. How will the loot be split?
Nov 2 Abhishek is at the centre of a circle of radius 100m. On the circle is a Lion. V_L = 4V_A. Help save Abhishek, by giving him a strategy that can always get him out of the circle, given that the Lion is very intelligent. While Abhishek stays within 25m of the centre of the large circle, his angular velocity exceeds that of the lion's. This means that he can stay on the opposite side of the lion with respect to the centre, no matter what the lion does. Keeping the lion there, Abhishek should move out to 25m away from the centre (and thus 125m away from the lion). Then, Abhishek should beeline for the edge of the circle, which is 75m away. Abhishek's exit point is 100\pi away from the lion and since this is more than 300m, the lion cannot catch Abhishek.
Nov 4 Dmitry is at the centre of a stadium of radius 100m without any exit. A Lion is also in the circle. V_D = V_A. Given that Dmitry and the Lion are very intelligent, how long can Dmitry survive? Hint: Can you find a sequence of points,so that the lion cannot catch Dmitry when he goes from one point to the next point, along the line connecting the two points? Clearly, if the distances of these line segments sum up to infinity, then Dmitry can run forever. -Yujia
Nov 7 (Fall reading break - No classes)
Nov 9 Can you find two irrational numbers x and y such that x^y is a rational number? Take x=y=\sqrt2, either x^y is rational and we are done, or x^y is irrational and we change the value of x to \sqrt{2}^\sqrt{2} so x^y=2 so the answer is yes.
Nov 14 Can you find a continuous f: [0,1] -> [0,1] with f(0) = 0 and f(1) = 1 which is differentiable with Df = 0 except on a set of measure 0?
Nov 16 Can you cover a diameter 100 disk with 99 (possibly overlapping) 100 x 1 bands?
Nov 18 No riddle. No solution.
Nov 21 n ants walking towards m ants on a wire. All of them have the same velocity. When any two ants meet, a bang is heard. How many bangs are heard all together? There is a long way and there is a short way. Though the long way is long, the thought process is more general.

W.L.O.G, assume n is less than or equal to m. When the two "head" ants hit each other, they go back and cause the "tail" ants go away. So you hear a total of (n-1)+(m-1)+1 bangs in this first propagation.Now that the "tail" ants leave the group, we are left with n-1 ants on one side, m-1 ants on the other side, each going towards each other at the same velocity. Repeat the same reasoning as above, we will here (n-2)+(m-2)+1 bangs, and so on. This process will end after n times since n is smaller than or equal to m. Sum up the number of bangs by propagations, we conclude n*n+m*n-n *(n+1)+n which is m*n bangs will be heard. Alternatively, one can consider the momentum of each ant. W.L.O.G, assume each ant has unit 1. We keep track of them by the arrows that represent their momentum. It is clear a bang is heard when two arrows intersect each other. But the arrows just just cross through each other after the collision. So the question is essentially asking how many times do arrows intersect each other. Well, there are n on one side, going in one direction, and m arrows on the other side. So they intersect in total n*m times.... - Yujia P.S. the second solution was proposed by Wilson Wu after today's lecture.

Nov 23 n black/white-hat-wearing prisoners stand in a row; each one sees the hats ahead of them but not their own or the ones behind. At noon, each one must guess and shout the colour on their head, going from the back forward. If more than one is wrong, all are executed. Could they have devised a strategy in advance, to save themselves? The last guy in the row shouts black if he sees an even number of black hats in front of him, white if he sees an odd number of black hats in front of him. Then the second last guy could find out his color by finding whether the number of hats in front of him is even or odd. So as the nth last guy because he can know the color of hats of the guys behind him(except the last guy).
Tao Sun
Nov 25 Ahmad and Bonita are wearing hats. They know they bear consecutive positive integers, under the usual hat rules.


1. Dror: A, what number's on your hat? A: I dunno.
2. D: B, what number's on your hat? B: I dunno.
3. D: A, ... A: I dunno
....
257. D: A, what's on your hat? A: I know! It's ____.

Let n be any natural number. After the first 2n-1 th questions before they know, B knows his number is not 2n-1, else A will know his number is 2n. After the first 2n th questions, A knows his is not 2n, else by when B will know his number is 2n+1. This can be proved by induction. On the 256th, A knows his number is less than 257. If he saw 257 on B's hat, he would find out his number is 258 immediately. Else, if he say some number k bigger than 258, there are still two choices for him n-1 and n+1. So A's number is 258.
Tao Sun.
Nov 28 n prisoners. Each wears infinitely-many randomly-chosen b/w hats. Simultaneously each needs to point at a black hat on their head. How can they maximize the chance that they will all get it right? (better than 2^{-n}).
Really?

Theorem. You can't do better than 2^{-n}.

Proof by DBN. Looking at others gives each prisoner no information about themself, so each prisoners' choice is reduced to randomness. So each prisoner gets their hat right with probability 1/2. But then n prisoners together give (1/2)^n=2^{-n}, sad as this may be.

Nov 30 What is wrong with DBN's proof from November 28? The probabilities are not independent. Though the odds of saving a particular prisoner is a half, it is not the case for all n. Proof: each prisoner points to the kth hat on their head where k is the smallest integer such that the other n-1 prisoners have a black hat as their kth hat. The odds that this works are no less than the odds that all n prisoners obtain the same value of k, which happens \frac{1}{n+1} times (which is once out of all the times that the lowest ring of hats where all but one are of the same colour which can happen in n+1 ways).
Dec 1 Handout given in class. Class moved from Dec 2 to Dec 1.

Yujia:If you try to box the sphere by unit cube and argue the limit tends to 0, that is the beginning of a wrong solution. Equally absurd is to bound it by unit sphere.

Dec 5 Infinitely many black/white hat-wearing prisoners watch each other from around a round island. At the gong, they each have to guess their colour. Can they devise a strategy that will allow at most finitely many of them to go wrong? P.S. Neptune (god of sea) destroys those who guess wrong. Assume the axiom of choice. Group all possible hat assignments into equivalence classes where two assignments are equivalent if they differ by at most finitely many assignments. Use the axiom of choice to choose a representative out of every class. The wizards look at the others' hats and they all see as assignment that belongs to the same equivalence class. They each choose the representative assignment of that class and name their colour in that assignment. At most finitely many will get it wrong as the true assignment is also in that equivalence class.
Dec 7 Can you fold a rectangular piece of paper (perhaps many times) so that the result will have a longer perimeter than the original? A positive answer is unlikely. I will only provide some heuristic reasoning, you are welcome to correct me. It suffices to show for any polygon(not necessarily convex,as long as its edge numbers are finite),after each non-trivial folding (the notion of folding needs to be carefully defined, non-trivial means you did not do nothing), the perimeter is decreasing. Here's how to see it: look at the boundary of the new polygon after folding. If a segment was on boundary before the folding, this part did not contribute or reduce anything to the perimeter. Now, some segments that were on the boundary gets cover by the part that gets moved, and some segments that were previously in the interior of the polygon is now on the boundary. I argue one can use the triangular inequality repeatedly to show the new segments have smaller length than the segments that are cover by the folding.-Yujia
Jan 6 Is there a distance-reducing f: [0, 1]^2 \to R^2 (meaning, d(f(x), f(y)) \leq d(x,y)) such that \text{length}(Bd(f([0, 1]^2))) > 4?
Jan 9 Players A and B. A writes 1-...-18 on three cubes. B chooses one of 3. A chooses one of the remaining. Throw away the third; play dice war on money 1000 times.
Jan 11 Cars A,B,C,D drive in the Sahara Desert on generic straight lines and at constant speed; it is known that A meets B (they arrive at the same place at the same time), A meets C, A meets D, B meets C, and B meets D. Does C necessarily meet D?
Jan 13 Can you fit 4 a x b rectangles in one (a+b)^2 square? Can you fit 27 a x b x c boxes in one (a+b+c)^3 cube? Can you fit 256 a x b x c x d boxes in one (a+b+c+d)^4 box? Can you fit n^n a_1 x a_2 x ... x a_n boxes in one (a_1 + a_2 + ... + a_n)^n box?
Jan 16 No riddle. No solution.
Jan 18 On Z x Z, a visible roach R starts at (0, 0) and once a minute jumps to the northeast, up to a distance of 10. Meanwhile, an exterminator E can poison one grid point per minute, away from R. Can E trap R?
Jan 20 Infinite board. There are three pieces at the lower left. For each move, pick up one piece, remove it and place one new piece to the right and one new piece above, but only if these squares are unoccupied. Can you clear the bottom 3?
Jan 23 6 people attend a party. Show that there are 3 of them who either love or hate each other. Now, 17 people at the party. prove that you can find 3 people who love or hate or yellow (new emotion) each other. Part a) Consider one of the people at the party, DBN. He has some emotions towards the other 5 people, so he feels the same way about at least 3 of them. If any two of those three feel the same way about each other, we are done. If none of them do, then all three of them feel the opposite way about each other, so we are also done. Part b) Pick one person, for the other 16 people left, WLOG, there must exist 6 people the person love (16 = 5 + 5 + 6). If two of thoes six love each other, then you have 3 people love each other. Else, you have 6 people only hate or yellow each other, then follow the part a, there must exist 3 of the six either hate or yellow each other.
Jan 25 n red points and n blue points are placed on the plane with no 3 on the same line. Prove that it is possible to pair them up using n straight line segments so that no two of the segments will intersect.
Jan 27 The game of 15 is played as follows. Two players alternate choosing cards numbered between 1 and 9, with repetitions forbidden, so the game ends at most after 9 moves (or 4.5 rounds). The first player to have within their cards a set of precisely 3 cards that add up to 15 mins. Would you rather move first or second?
Jan 30 Meta-Riddle: Which two riddles that have been posed already does a magic square solve?
Feb 1 Four points form a perfect square in the plane. Can you turn that square into a larger one by a sequence of moves of the form (x, y)\mapsto(x, 2x-y) performed on pairs from within our four points?
Feb 3 Guest Riddle (Kodiak)! How many squares (of any orientation) with lattice point vertices are there in an m\times n rectangle?
Feb 6 Guest Riddle (Abhishek)! What is the product of the number of all of the hairs on all of the heads of all the people on planet Earth? Another riddle... Simplify this: (a - x) (b - x) ... (z - x). BALD PEOPLE! Some people have 0 hairs so the product is 0. The listed polynomial contains the term (x - x) = 0 so the product of all of the terms is also 0.
Feb 8 The Cantor set C is of measure-0. Is this also true for C+C = {x+y: x,y \in C}? Is it always that if B is measure-0, then so is B+B?
Feb 10 Can you hang a medal on 2 nails so that if you remove any one of them, the medal will fall? Same with 3 nails? Yes. Wrap clockwise around nail 1 (c1), clockwise around nail 2 (c2), counterclockwise around nail 1 (w1), counterclockwise around nail 2 (w2). We get c1c2w1w2. Removing nail 1 leaves c2w2, which is equivalent to not wrapping anything at all. The case for removing nail 2 is analogous. For three nails, we do c1c2w1w2c3c2c1w2w1w3. The reader is invited to check that this holds.
Feb 13 Ahmed and Betty live in different towns and have good 19th-century hardware (paper, pens, envelopes, boxes, locks, keys, etc., but nothing electronic). They'd like to communicate privately, via an untrusted intermediate, Dror, who routinely travels between their cities. Can they do that, even if they haven't coordinated anything in advance? Yes. Ahmed sends a box to Betty locked with a lock that only Ahmed has the key to, A. Betty, figuring out Ahmed's strategy, sends the box back with her own lock, B. Ahmed returns the box to Betty after having removed his lock with his key. Now the box only has lock B on it, which Betty can remove when she gets the box. Thus, they can communicate by sending messages placed in a box such as this one, sending it via Dror, who never has possession of the box when it is not locked.

A comment on the above solution: The above method seems to fail under a man-in-the-middle attack. That is, Dror, having seen that Ahmed has decided to send a locked box to Betty, can simply place his own lock on the box and return the box back to Ahmed, claiming that he is delivering Betty's response (there is no good way for Ahmed to tell that this is not in fact the case). Once Ahmed removes his lock from the box, Dror is free to read the message himself.

Feb 15 Can you colour the points of R^2 with 4 colours, so that no two points of distance exactly 1 have the same colour? Yes, use vertex coloring of a graph. If two points in R^2 have the distance of 1, the vertices represent them are connected by an edge. The minimal number of color we need to do vertex coloring equals the maximal number k of k-regular subgraph of the graph plus one. And it is imposible to construct a 3-regular subgraph for points in R^2.
Feb 17 Riddle on projector.
Feb 27 Riddle on board.
Mar 1 Riddle on board.
Mar 13 A mirror swaps left and right but not up and down. How does the mirror know?
Mar 17 Explain where this went wrong: 1=\sqrt{1}=\sqrt{(-1)(-1)}=\sqrt{-1}\cdot\sqrt{-1}=i\cdot i=i^2=-1.