2024 Qualifying Quiz

1. The picture below shows a variant of a famous paradoxical puzzle. On the left, we take two rectangles of area 60, and cut each one into two pieces. On the right, we rearrange the four pieces, and put them together into a single rectangle of area 119. How could this be?

   

   1. Explain what's wrong. (Similar paradoxes can be found under names such as "Chessboard paradox" or "Missing square puzzle". It's fine to look at a source that explains such a paradox, provided you cite it — and explain it in your own words.)
   2. Although two 5 × 12 rectangles cannot really be rearranged into a 7 × 17 rectangle, it is possible to take two a × b rectangles and cut them as shown in the picture above to make a c × d rectangle, with no paradox. What should the lengths a, b, c, d be (up to scaling, of course)?
   3. It is also possible to take three congruent rectangles, cut each one into two pieces, and rearrange them to form a single rectangle similar to the original three. How can we do this?

      Try to find an answer that lets you create a paradoxical decomposition of your own!

2. Kayla has two red boxes, two green boxes, and two blue boxes. Each of the six boxes contains a secret number. Kayla hands the boxes to Leo and asks him to write the letters A, a, B, b, C, and c, on the boxes. We will write #A, #a, #B, #b, #C, and #c to refer to the secret numbers inside these boxes.

   From there, the boxes go to Maya, who opens the boxes and reports the differences #A−#a, #B−#b, and #C−#c, (in that order). Next, the boxes go to Nathan, who opens the boxes and reports the sum of the numbers in the red boxes, the sum of the numbers in the green boxes, and the sum of the numbers in the blue boxes (in that order). The resealed boxes, along with Maya's and Nathan's reports, are then handed back to Kayla, who must determine the numbers in each of the boxes.

   Kayla expected Leo to label same-color boxes with the same letter, which would have made it easy for Kayla to figure the numbers: for example, knowing #A−#a from Maya and #A+#a from Nathan, Kayla could solve for #A and #a. However, to Kayla's surprise, Leo is color blind, so his labeling had nothing to do with the colors.

   1. For which of the labelings that Leo used is it still possible for Kayla to determine the six secret numbers? (Kayla can see which colors have which labels on them.)
   2. Generalize your answer to a problem with 2n boxes of n different colors, labeled with n different uppercase and lowercase letters.
3. Here is a curious fact you may not have known about mathematicians: when asked a yes-or-no question, number theorists will always tell the truth, while analysts will always lie. Be careful: if you ask someone a yes-or-no question, and they cannot answer either "yes" or "no" to it, then the universe explodes in paradox. For example, this happens if you ask an number theorist, "Is your answer to this question 'no'?"
   1. What yes-or-no question can be asked to both a number theorist and an analyst to cause the universe to explode in both cases?
   2. To try to prevent the universe from exploding in paradox, logicians have decided to act as paradox detectors. When you ask a logician a yes-or-no question, the logician will answer "yes" if asking the question to a number theorist would cause the universe to explode, and "no" otherwise. For example, if you ask a logician, "Is your answer to this question 'no'?" the logician will answer "yes".

      What yes-or-no question can be asked to a logician to cause the universe to explode?

4. A group of 11 Mathcampers decided to bake a rainbow unicorn sprinkle cake with 10 slices. Unfortunately they cannot split up the slices into smaller pieces, because they do not want to risk upsetting the unicorn. Each Mathcamper wants a slice of the cake (but not more, because Mathcampers aren't greedy). Each Mathcamper helped bake the cake to some extent. The Mathcampers have been assigned fractions x₁, x₂,. . ., x₁₁ representing their share of the credit in baking the cake, where 0 < x_i < 1/10 for each i, and x₁ + x₂ + . . . + x₁₁ = 1.
   1. How can you randomly distribute the slices of cake such that the i^th Mathcamper has a probability of exactly 10x_i of getting a slice of cake?
   2. Generalize your solution to distribute k slices to n campers, for all k and n with n > k ≥ 1.

      As before, the Mathcampers have been assigned fractions x₁, x₂,. . ., x_n representing their share of the credit in baking the cake, where 0 < x_i < 1/k for each i, and x₁ + . . . + x_n = 1; for each i, you want the i^th Mathcamper to have a probability of exactly kx_i of getting a slice of cake.

   3. Suppose that, in the setup of part b, you do not know the value of k (the number of slices). Instead, you will put the Mathcampers in a random order, according to some strategy, and then serve slices of cake in that order until the cake runs out. Is there a way to do this so that for each i, the i^th Mathcamper will have a probability of exactly kx_i of getting a slice of cake — no matter what k turns out to be? (You may still assume that we have 0 < x_i < 1/k for all i, and x₁ + . . . + x_n = 1.
5. "Half stitching" is a form of embroidery which makes images out of diagonal stitches in a square grid. Our images will all be created from a single thread, which alternates traveling in straight lines (called stitches) along the front and the back of the grid:
   • The front of the grid is where the image is formed. Here, each stitch goes from a point (x,y) either to (x+1,y+1) or (x−1,y−1). We say that we stitch a square if a stitch on the front follows its diagonal (from top right to bottom left or from bottom left to top right).
   • The back of the grid is not part of the image. Here, each stitch can follow any straight line — but it must travel a positive distance, because if you end a stitch where it started, it will unravel.
   This problem is about minimizing the total length of thread needed to stitch a given pattern. For example, Figure 1e and Figure 1f (with front stitches in red and back stitches in blue) have the same pattern stitched, but the thread is 2√2 + 2√5 units long in the first case and only 2√2 + 2 units long in the second case.

   

   

   

   

   

   

   1. Show that the minimum length of thread (front and back) needed to stitch every square in an m×n rectangular grid is mn(√2 + 1) − 1. An example with m=3 and n=4 is shown in Figure 1a.
   2. A comb with n teeth is a pattern of width 2n − 1 and height 2 that stitches every square in the bottom row and every other square in the top row; an example of this pattern with n=4 is shown in Figure 1b. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of n?
   3. A tall comb with n teeth is a pattern of width 2n − 1 and height 3 that stitches every square in the bottom row and every other square in the top two rows; an example of this pattern with n=4 is shown in Figure 1c. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of n?
   4. A wide comb with n teeth is a pattern of width 5n − 4 and height 2 that stitches every square in the bottom row and every fifth square in the top row; an example of this pattern with n=3 is shown in Figure 1d. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of n?
   5. Can you prove anything in general about the minimum length of thread needed to stitch a pattern?
6. You may have heard of the Borromean rings (a famous pattern of 3 equal circles) or the Olympic rings (a famous pattern of 5 equal circles). The unchanging rings (which aren't famous because we just made up the name) are a pattern that can be made from different numbers of circles, with some special points on them marked.

   A system of unchanging rings must satisfy three unchanging rules:

   1. If two circles meet at a marked point, they share exactly two marked points.
   2. If two marked points lie on a common circle, they must share exactly two common circles.
   3. We can get from any circle to any other by some number of hops along marked points.

   One possible system of unchanging rings is shown below:

   

   1. Draw a system of unchanging rings with more than 4 circles, all equal in size.
   Maybe you thought this problem was about geometry? Just kidding! You see, there is a special kind of circle called a math circle: it's not a geometric object, but a group of people doing math together. Let's say that a "marked point" in such a case is a person participating in one or more of the math circles. We can form a system of unchanging rings out of math circles as well, by satisfying the unchanging rules.
   2. Prove that every system of unchanging rings (whether made up of ordinary circles or math circles) has an unchanging constant n, such that every circle contains exactly n marked points, and every marked point is contained in exactly n circles. (In the example drawn above, n=3.)
   3. In a system of unchanging rings with unchanging constant n, what is the maximum number of circles?
   4. For some n, find a nonempty system of unchanging rings with unchanging constant n such that it has fewer circles than the maximum you found in part c.

Problem #3 is due to Leo Kargin (MC 2022–2023). Problem #4 is due to Maya Kalai (MC 2023). Problems #1, #2, #5, and #6 were written by the Mathcamp staff.