Test Test
Shannon sits down to a history exam and discovers the following surprising directions at the top of the test: “You do not have to do all of the questions on this test. Simply make sure you answer at least two of the first three, four of the first seven, five from the middle third of the test, six of the last eleven, and three of the last five, and your exam will be eligible for full marks.”
What is the minimum possible number of questions Shannon might have to answer to receive full marks, for any test consistent with these instructions?
Late Show
Willow gets the syllabus for a twelve-week linguistics class that meets once per week and notices an unusual item. “Late Policy: you may arrive on time or late to any class, at your own discretion, with the following exception: if you are late to two classes in a row, then you may only be late to one more class the entire rest of the semester.” This starts Willow wondering about the patterns of on-time and late arrivals that the professor would allow…
How many different sequences of on-time and late arrivals over the course of the semester are allowed by the professor’s policy?
Solutions to Weeks 29, 30, and 31
Talking Midpoints. Note that the midpoint of two points `(a,b)` and `(c,d)` with integer coordinates is `((a+b)/2,(c+d)/2)` and has integer coordinates if `a` and `b` are both odd or both even, and `c` and `d` are both odd or both even. Hence, the 24 points may be divided into four categories: (odd,odd), (odd, even), (even, odd), and (even,even). Only pairs of points in the same category will have integer-coordinate midpoints. The question now becomes, how to divide the points into four categories to minimize the number of pairs of points in the same category? Note that if any category has `n` members and another category has `m` members with `n > m +1`, then by moving a point from the first category to the second, we lose `n-1` pairs from the first category (the pair of the moved point with each other point in the category) and gain only `m` pairs (the pair of the moved point with each point in the second category). That action reduces the number of pairs. Hence, at the minimum number of pairs, there cannot be any category with two more points in it than any other category. This happens only with six points in each category, in which case there are `({::}_2^6) + ({::}_2^6) + ({::}_2^6) + ({::}_2^6)`, or 60 pairs of points in the same category.
Split Vote. To know what the prospectors will do, we need to examine what will happen to each in turn should he or she become the oldest prospector remaining in the group. We start with the youngest prospector, i.e., what happens if the first 57 plans are all rejected and the youngest prospector is the only one left. Obviously he or she pockets all 60 nuggets (60 being the answer to the previous problem). Hence, if it comes down to just two prospectors, the older prospector has no hope. The younger prospector can guarantee receiving all of the nuggets simply by rejecting whatever the older prospector proposes (even giving the younger prospector all of the nuggets, since the younger prospector prefers to see the older one ejected from the International Prospector’s Union.) So if it comes down to this second-youngest prospector, he or she is doomed. Similarly, the third (youngest) prospector is doomed; if the youngest prospector votes no, there is no way the third prospector’s plan can get two more yes votes than no, and the third prospector will be ejected from the Union (if it comes down to his or her proposal).
This means that if the fourth prospector is proposing a plan, the second and third prospectors will vote for it no matter what the plan is (even if they get no nuggets!) in order to avoid being ejected to the Union. Since the fourth prospector can also vote for his or her own plan, a proposal of keeping all the nuggets will win. Hence if it comes down to the fourth prospector, he or she will get all the nuggets and the other three will get none.
Now consider the fifth prospector. He or she can’t possibly get the fourth prospector’s vote, because the fourth prospector has all of the nuggets coming anyway if the fifth prospector’s plan fails. Hence, the fifth prospector needs the votes of all of the first three, which he or she can win by proposing to give each of them one nugget, more than they would get under the fourth prospector’s plan, should the fourth prospector get the chance to propose. Thus, the fifth prospector would get 57 nuggets, the fourth zero, and the other three one.
Moving on to the sixth prospector, he or she needs three votes from the first five, which with his or her own vote will guarantee two more yeas than nays. Since the fourth prospector got zero in the previous plan, his or her vote is the cheapest to buy, for one nugget. And now the sixth prospector needs two votes from the first three, by giving them two nuggets each. It doesn’t matter which of these prospectors the sixth prospector pays off, so it might as well be random. Hence, the first three prospectors each have a 2/3 chance of getting two nuggets and a 1/3 chance of getting zero nuggets, the fourth prospector gets one nugget, the fifth prospector gets zero nuggets, and the sixth prospector gets 55 nuggets.
For the seventh prospector, now the fifth prospector is the cheapest at one nugget, and the earlier four prospectors each cost two nuggets to bribe — for the first three this is because they prefer the sure two nuggets in hand to the 2/3 chance of two nuggets next time, and for the fourth it is because two nuggets are better than one. The seventh prospector needs three of these four votes, so the first four prospectors have a 3/4 chance of getting two nuggets, the fifth prospector gets one nugget, the sixth prospector gets none, and the seventh prospector gets 53 nuggets.
Continuing in this fashion, we find that the odd numbered prospectors get the same number of nuggets as their predecessor, and the even numbered prospectors each get two fewer than their predecessors. Hence, there is a plan that will keep the oldest (58th youngest!) prospector in the union, namely, to give the 56th prospector one nugget, the 57th zero nuggets, 28 of the first 55 prospectors at random two nuggets each, and to keep 3 nuggets for him or herself.
Dream Sequence. The first step is simply to write down the (beginning of) the (infinite) expression the examiners are describing. If you follow what they say, it is `sqrt{1+3sqrt{1+4sqrt{1+5sqrt{1+6sqrt{1+cdots}}}}}`. A common technique in a case like this is to look for a copy of the whole expression somewhere inside itself, to produce an equation for the value of the whole expression. But that doesn’t happen here; instead of the expression appearing inside itself, all of the coefficients have increased by one. That suggests that if we look at `f(x) = sqrt{1+x sqrt{1+(x+1)sqrt{1+(x+2)sqrt{1+(x+3)sqrt{1+cdots}}}}}`, then `f(x)` will satisfy `f(x) = sqrt{1+xf(x+1)}`. So the problem is to find such a function `f`, and then we can just evaluate `f(3)`.
Rewriting the condition, we want `f(x)^2 = 1 + xf(x+1)`. Since this identity only involves powers and multiplication by `x` and adding constants, it is reasonable to wonder if there is a polynomial in `x` that satisfies the identity. If there is, then by comparing terms on the left and right, the constant term of `f` must be either +1 or -1. Moving on to the next term, if `f(x) = cdots cx^2 + bx +- 1`, then by comparing the coefficients of the constant term, we get that `+-2b = cdots + c + b +- 1`. This is a tricky equation to solve, as it has infinitely many variables (!), but it has one “simple” solution: `b=1` and `c` and all the higher coefficients equal to 0. Thus, possibly `f(x) = x + 1` is a solution, and plugging into the identity, we find that `x^2 + 2x + 1` is equal to `1 + x(x+2)`. Thus, the function `f(x)` really is `x+1`, and so the answer is `f(3)`, or 4.
Listen up, teammates. This problem is a tribute to the renowned mathematician Srinivasa Ramanujan, who once said that his muse wrote the answers to the problems he was contemplating on his tongue in the night, and all he had to do was speak them. Ramanujan dreamt up this problem and its deceptively simple answer. Look for an upcoming film about his remarkable life.
Alien Arithmetic. First, what does it mean for Polly not to know the two numbers? It means that the product she receives from the alien factors in two different ways, with both factors between 3 and 121 [corrected from the originally published 97], inclusive. As an example (in fact, the smallest such example), if the alien tells Polly 24, then the numbers could either be 3 and 8 or 4 and 6. On the other hand, if Polly hears the product of two primes, then she will know exactly what the numbers are; for example, if the product is 15, then the numbers must be 3 and 5. Similarly, if she hears four times a prime, then she knows exactly what the numbers are, since two is not allowed; for example, if the product is 12, then the numbers must be 3 and 4, since 2 and 6 is not allowed. If she hears twice the square of a prime, then she knows the numbers, again because the two is not allowed as a factor by itself; an example of this is 18, which must break down as 3 and 6, since 2 and 9 is not allowed. In fact, these are all of the cases in which Polly knows the numbers just from the product; if the product is not in one of these categories (product of two primes, four times a prime, twice a prime squared) then Polly will not know the numbers.
So what does it mean for Sam to know that Polly can’t tell what the numbers are? It means that for every way of breaking the sum he hears into two numbers that add up to it, the product of those two numbers is one for which Polly can’t tell what the numbers are, i.e. not the product of two primes, four times a prime, or twice a prime squared. For example, Sam cannot have the sum 8, because then the numbers would be 3 and 5 with product 15, and we just saw above that Polly can figure out the numbers from a product of 15. But Sam could have the sum 19, because 3×16 = 48, 4×15 = 60, 5×14 = 70, 6×13 = 78, 7×12 = 84, 8×11 = 88, and 9×10 = 90 are all numbers for which Polly can’t figure out the product.
So now we need to figure out what all numbers Sam could have based on his first statement. It’s easier to figure out numbers he can’t have. So, he can’t have any even number, because then it could be written as the sum of two odd primes (that’s called Goldbach’s Conjecture, and it has been verified for all even numbers up to some huge cutoff), and Polly could figure out those two primes from their product. He can’t have any prime number plus four, because then it could be written as four plus a prime, and Polly could figure out the numbers were four and that prime. And he can’t have any number of the form three times a prime, because then it could be written as that prime plus twice that prime, and Polly could figure out the numbers from their product, twice a prime squared. And just as those were the only three categories in which Polly can figure out the two numbers, these are now the only general categories of numbers that Sam can’t have. However, as the numbers become larger, there are additional numbers not in these families that Sam can’t have because the factors get out of the range from 3 to 97. For example, 79 = 8 + 71, and in smaller cases you could rewrite 8×71=568=4×142, but 142 is out of the range specified by the alien. Therefore, Polly actually can tell what the two numbers are if she hears a product of 568. If you go through all of the numbers up to 120+121 (the largest possible sum), the only sums that Sam could have (i.e., not even, not a prime plus four, and not three times a prime, and not too large) are 13, 19, 25, 29, 31, 37, 43, 49, 53, 55, 59, and 61.
So what does it mean when Polly says that now she does know the two numbers (after hearing Sam say that he knows she doesn’t)? It means that she has an ambiguous product with the property that only one of its possible factorizations into two numbers adds up to one of the numbers on Sam’s list (since Polly now knows Sam heard one of those numbers). For example, if Sally had the product 30, she would not know the two numbers — they could be 3 and 10 or 5 and 6. But then when she hears Sam knows that she can’t tell, she can rule out 5 and 6. Why? Because they add up to 11, and 11 is not on the list of numbers which allow Sam to realize Polly doesn’t know the numbers; if Sam heard 11, the numbers could be 4 and 7, and Polly can deduce 4 and 7 from their product. Therefore, in that scenario, Polly is left with only the possibility of 3 and 10 to get a product of 30, so she knows the numbers. On the other hand, if she had a product of 84, then she would be confused between 3×28, 4×21, 6×14, and 7×12. And then hearing that Sam knew she could not tell the numbers would not help, because both 4+21=25 and 7+12=19 are sums that Sam might have that would allow him to say that Polly doesn’t know the numbers. So Polly can’t tell which is the case, and so could not then claim to know the numbers.
So, for which products exactly does Sam revealing that he’s sure that Polly doesn’t know the numbers actually allow Polly to deduce the numbers? We classify them by which of Sam’s possible sums from the list above apply.
For 13, then Polly can figure out 30=3×10, as described above; she can figure out 36=4×9, since the only other factorization into 3 and 12 has the sum 15, not on Sam’s list; she can figure out 40=5×8, because 4+10=14; and she can figure out 42=6×7, since 3+14=17.
Before going on to other sums, how in the end will we solve this problem? We need to use Sam’s last statement, that in the end he knows the numbers, too. What does that mean? It must mean that there’s only one product for Polly’s sum that she can figure out by virtue of knowing that the sum is on Sam’s original list. So Sam could not have had 13, because there are four different products that Polly could then decode, so he certainly can’t tell what the numbers are.
This means as we go through Sam’s possible sums, we can stop as soon as we find two products with that sum which Polly can decode, because then it’s already not going to work for Sam to figure out the numbers. We don’t have to list all of the products Polly can decode.
So turning to 19, Polly could have 48=3×16, because both of 4+12 and 6+8 are even (and hence not on Sam’s list). But she could also have 60=4×15, because none of 3+20=23, 5+12=17 or 6×10=16 are on Sam’s list. So Sam’s sum is not 19.
How about 25? Polly could have 66=3×22, because 6+11=17 is not on Sam’s list. And she could have 114=6×19, because 3+38=41 is not on the list. Hence 25 is out.
Now when we get to 29, we discover that the product could be 78=3×26, but 78 could also result from 6 and 13, which sum to 19, which is also on Sam’s list, and so would remain ambiguous. And similarly, 100=4×25 but 5+20 on Sam’s list. 120=5×24 but 3+40 on list. 138=6×23 but 3+46 on list. 154=7×22, but 11+14 on list. 168=8×21, but 7+24 on list. 180=9×20, but 4+45 on list. 190=10×19, but 5+38=43 on list. 198=11×18, but 9+22=31 on list. 204=12×17, but 4+51=55 on list. And 210=14×15, but 10+21=31 on list. Only with 208=13×16 can Polly then assert that she knows the numbers after Sam’s first statement, because both 8+26 and 4+52 are even, and hence not on Sam’s list. So there is only one set of numbers that would induce Polly to make the claim she did, and Sam can figure out what the numbers are. So that should give us the answer.
But just to be sure, note that for 31, Polly could have 108=4×27, because the only other odd sums corresponding to 108 are 12+9=21 and 36+3=39, neither of which is on Sam’s list. Or Polly could have 130=5×26, because 10+13=23 is not on Sam’s list. So 31 is out.
For 37: 102=3×34, but 6+17=23 not on list, and 160=5×32, but all the other sums of two factors of 160 are even. No good.
For 43: 352=11×32, but all of the other sums of two factors of 352 are even; and 222=6×37, but 3+74 = 77 is not on Sam’s list, so Polly would know the numbers in either case that she had the product 352 or 222. So Sam can’t then figure out the two numbers, so 43 is out.
For 49: 328=8×41, and all of the other sums of two factors of 328 are even; and 544=17×32, and all of the other sums of two factors of 544 are even. Hence, 49 is no good.
For 53: 592=16×37, and all of the other sums of two factors of 592 are even; and 682=22×31, but the only other factorization of 682, into 11 and 62, has sum 73 which is not on Sam’s list. So Rachel could decode both 592 and 682, so 53 is not Sam’s original number.
For 55: 376=8×47, and all of the other sums of two factors of 376 are even; and 736=23×32, and all of the other sums of two factors of 736 are even. So 55 is out.
For 59: 688=16×43, and all of the other sums of two factors of 688 are even; and 318=6×53, but 3+106 = 109 is not on Sam’s list. So 59 is out.
Finally, for 61: 424=8×53, and all of the other sums of two factors of 424 are even; and 928=29×32, and all of the other sums of two factors of 928 are even. So 61 is eliminated as well.
That means that 29 is the only sum that Sam could get for which Polly can only decode one of her possibilities based on the knowledge she gleans from Sam, thereby cluing Sam into the answer as well. In particular, it’s the combination of 13 and 16 that works, so those are the alien’s numbers. Just to check: in this scenario, Sam gets sum 29, and checks that in every way to break it into two numbers that sum to 29, the product of those two numbers does not uniquely determine the pair. So he is able to say that Polly does not know the numbers. But Polly had 208, so she knew the numbers were one of 13,16 or 26,8, or 52,4. But 34=26+8 and 56=52+4 are both even, so Polly knows that if Sam had either of those sums, he could not have been sure that Polly did not know the answer (for example, with 34, the two numbers could have been 3 and 31, which Polly could figure out immediately from their product 93, and similarly 56 could have come from 3+53.) Therefore, Polly can now conclude that the numbers are 13 and 16. And since all of the other options for a sum of 29 remain ambiguous but Polly says she knows the numbers, Sam can now realize that they are 13 and 16 as well.
Recent Weeks
Week 31: Alien Arithmetic & Dream Sequence, solution to Treasure Trek
Week 30: Split Vote & Treasure Trek, solution to Patriotic Packing
Week 28: Closing Times & Midpoint Well Taken, solution to Fancy Dice
Week 27: Fancy Dice & Gothic Arc, solution to HIJKMNOP
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.
[asciimathsf]
