2. Blogging
3. Jun 20, 2017

A few semesters ago we launched a course for mathematics majors, called MAT 220: Introduction to Mathematical Reasoning. The focus of the course is on reasoning and communication through problem solving and written mathematical arguments in order to provide students with more experience and training early in their university studies. The goal is for the students to work on interesting yet challenging multi-step problems that require almost zero background knowledge. The hope is that students will develop (or at least move in the direction of) the habits of mind of a mathematician. The problem solving of the type in this course is a fundamental component of mathematics that receives little focused attention elsewhere in most mathematics programs. I love teaching this course!

This past semester I taught the course for the second time. You can find the syllabus, list of problems, etc. for the Spring 2017 semester by going here. On the students’ final exam, I asked them which problem was their favorite from the semester. Below is the list of problems that they mentioned including the number of votes that each received. The level of difficulty of the problems covers the spectrum. Some of these are not easy. Have fun playing!

1. (6 votes; several students commented that their favorite part about this problem was how excited the student was that solved it) An overfull prison has decided to terminate some prisoners. The jailer comes up with a game for selecting who gets terminated. Here is his scheme. 10 prisoners are to be lined up all facing the same direction. On the back of each prisoner’s head, the jailer places either a black or a red dot. Each prisoner can only see the color of the dot for all of the prisoners in front of them and the prisoners do not know how many of each color there are. The jailer may use all black dots, or perhaps he uses 3 red and 7 black, but the prisoners do not know. The jailer tells the prisoners that if a prisoner can guess the color of the dot on the back of their head, they will live, but if they guess incorrectly, they will be terminated. The jailer will call on them in order starting at the back of the line. Before lining up the prisoners and placing the dots, the jailer allows the prisoners 5 minutes to come up with a plan that will maximize their survival. What plan can the prisoners devise that will maximize the number of prisoners that survive? Some more info: each prisoner can hear the answer of the prisoner behind them and they will know whether the prisoner behind them has lived or died. Also, each prisoner can only respond with the word “black” or “red.” Now, suppose that there are 11 prisoners. Describe a strategy for maximizing the number of prisoners that will live. What if there are $n$ prisoners?
2. (4 votes) Four prisoners are making plans to escape from jail. Their current plan requires them to cross a narrow bridge in the dark that has no handrail. In order to successfully cross the bridge, they must use a flashlight. However, they only have a single flashlight. To complicate matters, at most two people can be on the bridge at the same time. So, they will need to make multiple trips across the bridge, returning the flashlight back to the first side of the bridge by having someone walk it back. Unfortunately, they can’t throw the flashlight. It takes 1, 2, 5, and 10 minutes for prisoner $A$, prisoner $B$, prisoner $C$, and prisoner $D$ to cross the bridge and when two prisoners are walking together with the flashlight, it takes the time of the slower prisoner. What is the minimum total amount of time it takes all four prisoners to get across the bridge?
3. (3 votes; we encountered several variations of this problem) Suppose you have 12 coins, all identical in appearance and weight except for one that is either heavier or lighter than the other 11 coins. What is the minimum number of weighing one must do with a two-pan scale in order to identify the counterfeit? Now, suppose you have $n$ coins. For which $n$ is it possible to devise a procedure for identifying the counterfeit coin in only 3 weighings with a two-pan scale?
4. (3 votes) 100 prisoners are isolated in individual jail cells with no way to communicate. They are currently serving life sentences. Due to an overcrowded prison, the jailer decides to offer the prisoners the following deal. There is a room with nothing in it except a light switch (that starts in the off position). At random, the jailer will escort a single prisoner into the room with the light switch. After 5 seconds, the jailer will escort the prisoner back to his/her jail cell. The jailer will repeat this over and over again. He tells each of the prisoners that if one of the prisoners can indicate when every prisoner has been in the room with the light switch at least once, he will let all the prisoners go. However, if a prisoner erroneously states that each prisoner has been in the room with the light switch, then all the prisoners will be executed. Before beginning, the jailer gets all 100 prisoners together and gives them 5 minutes to come up with a plan. What should their plan be? It’s important to note that the jailer is choosing prisoners at random to take in the room. That is, by chance, the same prisoner may be escorted to the room several times in a row. Also, your task is to devise a scheme for the prisoners to communicate with the light switch. You shouldn’t bother searching for other ways for the prisoners to communicate.
5. (2 votes; we encountered several variations of this problem) A soul swapping machine swaps the souls inside two bodies placed in the machine. Soon after the invention of the machine an unforeseen limitation is discovered: swapping only works on a pair of bodies once. Souls get more and more homesick as they spend time in another body and if a soul is not returned to its original body after a few days, it will kill its current host. Bart (B), Lisa (L), Homer (H), Marge (M), and Ned (N) were involved in a soul-swapping bonanza that resulted in Bart’s soul being Lisa’s body, Lisa’s soul being in Homer’s body, Homer’s body being in Marge’s body, Marge’s soul in Ned’s body, and Ned’s soul being in Bart’s body. Thankfully, Krusty the Clown (K) and Santa’s Little Help (S) never utilized the machine and are available to help put everyone’s soul back in the appropriate body. Find a way to return all the souls to their respective owner.
6. (1 vote; see the discussion of Problem 86 on the class journal for Monday, May 1) The first vote counts of the papal conclave resulted in 33 votes each for candidates A and B and 34 votes for candidate C. The cardinals then discussed the candidates in pairs. In the second round each pair of cardinals with differing first votes changed their votes to the third candidate they did not vote for in the first round. The new vote counts were 16, 17 and 67. They were about to start the smoke signal when Cardinal Ordinal shouted “wait”. What was his reason?
7. (1 vote) Recent archaeological work on Mars shows a number of sites, each site containing a large mound of white spheres, each about the size of a tennis ball. Each ball contains a jewel. The jewels come in many different colors, but at each site, strictly more than half of the spheres contain jewels of the same color. When two balls are brought together, they both glow white if their internal jewels are the same color; otherwise, no glow. You have recently stumbled on a cache of 13 spheres. In how few tests can you find a sphere that you are certain holds a jewel of the majority color?
8. (1 vote) A certain fast-food chain sells a product called “nuggets” in boxes of $6, 9$, and $20$. A number $n$ is called nuggetable if one can buy exactly $n$ nuggets by buying some number of boxes. For example, $21$ is nuggetable since you can buy two boxes of six and one box of nine to get 21. Here are the first few nuggetable numbers: $6, 9, 12, 15, 18, 20, 21, 24, 26, 27,\ldots$ and here are the first few non-nuggetable numbers: $1,2,3,4,5,7,8,10,11,13,\ldots$. What is the largest non-nuggetable number?
9. (1 vote) A signed permutation of the numbers 1 through $n$ is a fixed arrangement of the numbers 1 through $n$, where each number can be either be positive or negative. For example, $(-2,1, -4,5,3)$ is a signed permutation of the numbers 1 through 5. In this case, think of positive numbers as being right-side-up and negative numbers as being upside-down. A reversal of a signed permutation is the act of performing a 180-degree rotation to some consecutive subsequence of the permutation. That is, a reversal swaps the order of a subsequence of numbers while changing the sign of each number in the subsequence. Performing a reversal to a signed permutation results in a new signed permutation. For example, if we perform a reversal on the second, third, and fourth entries in $(-2,1,-4,5,3)$, we obtain $(-2,-5,4,-1,3)$. The reversal distance of a signed permutation of 1 through $n$ is the minimum number of reversals required to transform the given signed permutation into $(1,2,\ldots,n)$. It turns out that the reversal distance of $(3,1,6,5,-2,4)$ is 5. Find a sequence of 5 reversals that transforms $(3,1,6,5,-2,4)$ into $(1,2,3,4,5,6)$.
10. (1 vote) My Uncle Robert owns a stable with 25 race horses. He wants to know which three are the fastest. He owns a race track that can accommodate five horses at a time. What is the minimum number of races required to determine the fastest three horses?
11. (1 vote) Each integer on the number line is colored with exactly one of three possible colors, red, green, or blue, according to the following two rules:
    • (Rule 1) The negative of a red number must be colored blue;
    • (Rule 2) The sum of two blue numbers (not necessarily distinct) must be colored red. Using this information, determine all possible colorings of the integers that satisfy these rules.
12. (1 vote) Annie, Bob, and Cristy are sitting by a campfire when Cristy announces that she is thinking of a 3-digit number. She then tells Annie and Bob that the number she is thinking of is one of the following: $515, 516, 519, 617, 618, 714, 716, 814, 815, 817$. Next, Cristy whispers the leftmost digit in Annie’s ear and then whispers the remaining two digits in Bob’s ear. The following conversation then takes place:
    • Annie: I don’t know what the number is, but I know Bob doesn’t know too.
    • Bob: At first I didn’t know what the number was, but now I know.
    • Annie: Ah, then I know the number, too. From that information, determine Cristy’s number.
13. (1 vote) Consider a $8\times 8$ grid with light-up squares. In the starting configuration, some subset of the squares are lit up. At each stage, a square lights up if at least two of its immediate neighbors (horizontal or vertical) were “on” during the previous stage. It’s easy to see that for the starting configuration in which eight squares along a diagonal of the board are lit up, the entire board is eventually covered by “on” squares. Several other simple starting configurations with eight “on” squares also result in the entire board being covered. Is it possible for a starting configuration with fewer than eight squares to cover the entire board? If yes, find it; if no, give a proof.
14. (1 vote) Suppose we draw $n$ distinct lines in the plane that have the maximum number of unique intersections. How many intersections are there? The resulting configuration partitions the plane into disjoint regions (some of which are polygons with finite area and some are not). Suppose we color each of the regions so that no two adjacent regions (i.e., share a common edge) have the same color. What is the fewest colors we could use to accomplish this?
15. (1 vote) The Infinite Hotel has rooms numbered $1,2,3,4,\ldots$. Every room in the Infinite Hotel is currently occupied. Is it possible to make room for one more guest (assuming they want a room all to themselves)? An infinite number of new guests, say $g_1, g_2,g_3,\ldots$, show up in the lobby and each demands a room. Is it possible to make room for all the new guests even in the hotel is already full? The full infinite bus brings new guests to the full infinite hotel. How can they stay at the hotel?
16. (1 vote) What size rectangles can be tiled with L-shaped trominoes?

A while back I wrote a similar post that highlighted 15 fun problems from the first time I taught the course. You’ll notice that there is some overlap between the two lists.