1617-257/Riddle Repository

From Drorbn
Jump to navigationJump to 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 .

Prof. A claims , so

Prof. B claims , so

Smart student says . Why is the derivative the sum of the Prof's solutions?

Sept 14 Can all of be covered by a set of disjoint, non-degenerate, circles? What about ? ?
Sept 16 Can you find uncountably many disjoint subsets of ?
Sept 19 Can uncountably many Y shapes be fit into ?
Sept 21 On any pair of potatoes, can you draw a pair of 3D congruent curves? Hint (Hover)
Sept 23 Can you find uncountably many subsets of 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 s.t. for any two of them A and B, (A B) or (B 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?
Oct 5 Can you write the function as ? (Credit: Yujia Yin) Yujia: This question is fairly funny if you have the right idea. Let's say you can find such and ,where k=1,2. Then sub y=0,1,-1, you see and 1 can be written as linear combinations of . 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.
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)
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.
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. = . Help save Abhishek, by giving him a strategy that can always get him out of the circle, given that the Lion is very intelligent.
Nov 4 Dmitry is at the centre of a stadium of radius 100m without any exit. A Lion is also in the circle. = . 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 is a rational number?
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.
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 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 ).
Really?

Theorem. You can't do better than .

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 . But then prisoners together give , sad as this may be.

Nov 30 What is wrong with DBN's proof from November 28?
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.
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 (meaning, ) such that ?
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 square? Can you fit 27 a x b x c boxes in one cube? Can you fit 256 a x b x c x d boxes in one box? Can you fit x x ... x boxes in one box?
Jan 16 No riddle.
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.
Jan 25 n red points and n blue points are placed in 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.