2018-2019
The Problem of the Fortnight is a bi-weekly contest problem offered by the Department of Mathematics and Computer Science. Anyone in the wider Wabash community may submit solutions: students, faculty, staff, and alumni. Submissions will be judged on their correctness and elegance. Authors of correct solutions will be acknowledged, and the best solutions will be posted. Repeat solvers win prizes! The student who solves the most problems in an academic year is declared FortKnight of the Year.
The Problem of the Fortnight for this academic year is a joint effort of Professors Gates & Cole.
Problem of the Fortnight #4: Arcs!
Suppose s is an arc of the circle of radius 1 centered at the origin of the xy-plane, and that s lies completely in the first quadrant.
If X is the area lying below s and above the x-axis and Y is the area to the right of the y-axis and to the left of s, prove that X+Y depends only on the arclength of s and not on the position of s. (There are multiple ways to solve this problem!) Please send answers by Friday, February 22 to Professors Gates (gatesz@wabash.edu) and Cole (colej@wabash.edu).
Problem of the Fortnight #3: Making Sense of Complicated Arithmetic.
A = (1/2 – 1/3) * (1/4 – 1/5) * (1/6 – 1/7) * … * (1/96 – 1/97) * (1/98 – 1/99)
B = (1/1 – 1/2) * (1/3 – 1/4) * (1/5 – 1/6) * …* (1/97 – 1/98) * (1/99 – 1/100)
The “…” indicates the pattern is to be continued in the middle in the obvious way. The symbol * indicates multiplication.
Which is bigger, A or B? And what is the ratio of the larger to the smaller? Give elegant demonstrations that don’t rely on simply calculating A & B in the straightforward (but tedious) way. Such demonstrations will easily provide answers to the same questions if A and B are made to go out any arbitrarily further distance.
The winner, with the best presentation of a correct solution, is Jim Brown. Congratulations! His solution was attached to the campus email: we'll get a link here soon! We also received correct solutions from John Smilie, who did an excellent job showing explicitly the generalization when the definitions extend to N instead of 100; Eric Dunaway, who did a nice job using product notation and correctly using notation with it; and Alex Rotaru, who also used some product notation, and made use of the factorial sign !, which is always fun.
Problem of the Fortnight #2: Wally Wabash v. Danny DePauw II: Game of Circles
A square with sides 50 cm long is drawn. Wally and Danny take turns drawing circles with radius between 1 cm and 5 cm inside the square. The circles are not allowed to intersect or be drawn inside another circle. The first player who cannot draw a circle in the remaining space inside the square loses. Wally has the honor of drawing the first circle. Does either player have a winning strategy? If so, describe it.
The eventual hint: the size of the square and radius of the circles are irrelevant to the solution of the problem except we must be able to fit at least one circle inside the square (otherwise, it is not a very interesting game!).
A correct solution was given John Maharry, Dave Maharry’s son:
Here’s my 1st player winning strategy. Play a circle in the center then on each turn play a symmetric circle to your opponent’s circle. Pretty sure you will always be able to play, no?
By “symmetric circle” is meant a circle of the same size as the one played by the opponent, and exactly opposite, across the center of the square. (To be precise, the symmetric circle is obtained from the opponent’s by rotating it 180 degrees about the center of the square.) Since Player 1 is always able to play, he will be able to make the last play. Since there is a minimum radius to the circles allowed to be played, they must eventually take up all the space.
Congratulations to John for finding the correct solution. Technically we can’t count him as the winner this week (he’s all grown up and out of his father’s house!), but we are grateful for his interest, especially since his was the only correct submission we received!
Problem of the Fortnight #1: Wally Wabash v. Danny DePauw in the Game "72."
Over Christmas break, Wally Wabash and Danny DePauw are back home in Indianapolis and are bored and so decide to play a game. On his turn, a player is allowed to play a whole number between 1 and 8, including 1 or 8. That number is added to the previous total. The total is never allowed to go over 72, and a player wins if his play brings the sum up to 72. Suppose Wally goes first. Which player has a guaranteed winning plan of action, and what is it? What happens if we change the game so that the player who brings the total to 72 loses?
Solution. The best solution was judged to be Brad Weaver's:
WIN ON 72
Player 2 can guarantee a win by ensuring the point total for each round = 9. For example, if Wally plays a 1, Danny should play an 8, or if Wally plays a 6, Danny should play a 3. resulting in a round 1 score of 9. Continuing this strategy, the total after each round will be 9, 18, 27, 36, 45, 54, 63, and finally 72.
LOSE ON 72
Losing on 72 can restated as winning on 71, since the only remaining play is a 1 to hit 72. In this scenario, Player 1 can guarantee a win by starting with an 8, and from that point on ensuring that player 2 + player 1’s next play = 9. With this strategy, after each turn for Player 1, the total will be 8, 17, 26, 35, 44, 53, 62, and finally 71. Player 2 will then lose on hitting 72.
Complete and correct solutions were also given by Eric Dunaway and Steve Hoffman. Thanks to all for their participation! This seemed to be a problem that engaged the interest of many people.
2017-2018
The FortKnight of the Year for this year was Kevin Sheridan. Congratulations!
This year's competition was run by Prof. Josh Cole.
Problem 8: The Unhelpful Ferry.
Camwise Hamgee and Rosamund Linen live in a row of 9 hobbit holes along a canal. A company called Drogo’s Transportation offers rides along the canal between the 9 hobbit holes. (The land paths are muddy and you have to walk through your neighbors’ yards.) The canal runs west to east, and Camwise’s hobbit hole is 2nd of the 9, whereas Rosamund’s is the 8th of the 9. Camwise, though a bit shy, fancies Rosamund, and they see each other often, using Drogo’s Transportation. However, it seems the fates are against them. For Camwise claims that most of the time when he sees the ferry, it is headed west, instead of east, the direction towards Rosamund. In this case an impatient Camwise waits for the ferry to finish its westward journey before getting on when it returns going east. And Rosamund likewise claims that when she sees the ferry, it is most of the time headed east, away from Camwise’s hobbit hole. Our task is to investigate what seems to be a dark conspiracy to keep them apart!
Part A: If Drogo’s Transportation has only one ferry boat, what is the probability that after he begins to wait, the first ferry seen by Camwise is headed in Rosamund’s direction? Answer the analogous question for Rosamund.
Part B: What if Drogo has two ferries? Answer the same questions.
Nicholas Glassmaker contributed the winning solution.
This problem is actually modeled on an elevator problem first posed by George Gamow and Marvin Stern (Puzzle-Math, Viking, 1958), first solved correctly by the famous computer scientist Donald Knuth, and which came to my attention through an article on it entitled “Elevators” that I read in Martin Gardner’s collection of Scientific American articles called Knotted Doughnuts (1986).
The equivalent elevator problem would have Camwise on the 2nd and Rosamund on the 8th of a 9 floor building. There we would imagine a total elevator circuit up and down to be 16 units. On the other hand, in the solution attached, the total path of the ferry is 18 units: the entirety of distances along the first and ninth hobbit holes are traversed. If it were entirely analogous to the elevator problem, the ferry would stop at the midpoint along the first and last hobbit holes. It is interesting how there are various ways to turn a discretely-described system into a continuous one. The dynamics of a solution are the same, however.
I re-dressed the statement of the problem in ferry language to reduce the probability of solution by google search, but the elevator setup is easier to understand and admits of only one reasonable continuous model. For this reason, I’ll discuss the solution in the language of elevators. When there is just one elevator, the answer is easy, though perhaps counterintuitive. If the elevator is headed down from 2 or up from 1, it’ll be headed in the right direction when it reaches Cam. Since a total circuit is 16 units, there is a 2/16 or 1/8 chance the elevator is headed the right direction when it reaches Cam. The situation for Rosamund is obviously isomporhic, so she also has a 1/8 chance that when the elevator comes it is going the right way. We might’ve thought, if we had given an answer without thinking, that the probability would be 50/50, since an elevator is either going up or going down. (This is the “all possibilities are equal likely” trap, the error behind a whole range of mistakes in probability theory, including the famous Monty Hall Problem.)
In Part B, Mr. Glassmaker carefully worked through the details of many contingencies; but Knuth gave an elegant solution based on the concept of an unbiased zone, which I wish to discuss for the corollary it immediately implies concerning the situation as we increase the number of elevators.
Consider the part of an elevator’s journey that begins at the fourth floor headed downwards, continues to the first floor, and then back up to the second. The length of this journey is 4 units (3 down, 1 up). Half the time, from floor 4 down to floor 2, if that elevator is the next to arrive at Sam’s floor, the elevator will be going the wrong way for him. If Cam begins waiting when the elevator is in the other half of this journey (down from 2 to 1, then back up to 2), the elevator will be going the right way when it reaches Cam. This part of an elevator circuit from floor 4 to 1 and up to 2 is therefore called the unbiased zone, since an elevator randomly positioned there has a 50/50 shot at being headed the right way when it gets to Cam.
Now, if there are two elevators and they are both are outside of the unbiased zone, they will be going the wrong way when they reach Camwise, no matter which gets there first. Since the length of the unbiased zone is 4 and the total length of an elevator circuit is 16, there is a ¼ chance that an elevator is in the unbiased zone. Thus the probability both elevators are not in the unbiased zone is ¾ x ¾ = 9/16. So the probability at least one elevator is in the unbiased zone is 7/16. Now for the zinger: even if there are two elevators in the unbiased zone, the chance the closest is going in the right direction must be ½! At first, this situation might seem to require a complicated conditional analysis; however, it is impossible in the unbiased zone that it could be more likely for the closest elevator to be headed one way or the other – whatever sorts of situation make the closest elevator going in the wrong direction have analogous sorts of situations of exactly the same measure, in which the closest elevator is going the correct direction.
Thus the probability, when there are two elevators, that the first seen by Cam is headed in the right direction, is (7/16) x (1/2) = 7/32, which is greater than 1/8, the probability the elevator is going in the right direction when there is only one. This makes sense, because although any given elevator is likely to be going the wrong direction, the ones going in the right direction tend to be closer to Cam and so more likely to get to him first in a situation with two elevators.
A nice feature of the unbiased zone is that it doesn’t matter at all how many elevators are in play, if there is at least one in the unbiased zone (and we possess no other information) the probability that the elevator that first gets to Cam is going the correct directions is ½. Now, imagine what happens as the number of elevators approaches infinity: the probability that at least one is in the unbiased zone approaches 1: thus the probability that the first elevator to reach Cam is going the right direction approaches 1 as the number of elevators goes to infinity.
Knuth was able to give a simple formula for the exact probability that the first elevator seen by Cam is going in the right direction, given that there are n elevators. (It is actualy not hard to compute, given the “unbiased zone” analysis above.) However, it is neat that one can see the probability goes to ½ in the limit without recourse to the specific formula for the situation of n elevators.)
Knuth parlayed the elevator problem into interesting insights into the theory of sorting lists, which is important for computer science. See Gardner’s abovementioned article for more details and the reference in Knuth. (Or, I’d be happy to supply references to anyone curious.)
Problem 1: Stolen Parking Places!
In the year 2070 Wabash has grown in size and requires parking passes to park on campus. In a faculty lot, there are exactly 47 spots, each reserved for a particular faculty member. One day Professor Alpha, the first to arrive, is thinking about his exciting lecture on mathematical induction, and accidentally parks in Professor Tesla’s space. Each professor who subsequently arrives will take his or her own spot if it is available; if not, he or she will randomly choose another spot. What is the probability that Professor Omega, who arrives last (the 47th of all 47), will be able to park in her own spot?
Solutions are due to Professor Cole by 4pm on Friday, October 6. Drop them off at Goodrich 108 or email them: colej@wabash.edu
For Problems of the Fortnight from longer ago: click here.