Simultaneous Remainders
Let x and y be two positive whole numbers such that x > y, with the properties that the remainder when xy is divided by 1008 is zero, and the remainder when x-y is divided by the answer to last week’s Test Test problem is also zero.
What is the smallest possible value of x?
Subtle Sequences
Let `a_n` and `b_n` be sequences of real numbers satisfying two relationships:
`a_{n+1} = a_na_1 – b_nb_1`
`b_{n+1} = b_na_1 + a_nb_1`
Suppose further that `a_1= (1+sqrt5)//4` and `b_1=sqrt{(5-sqrt5)//8}`.
What is `a_{2016}`?
Solution to Week 32
Late Show. There are a lot of possible sequences of being on time and late, so it would be very difficult to write them all out. So it’s best to begin by simplifying the problem, and the easiest way to to do that is to consider a smaller number of classes in the semester. For example, if the class met just once, you could be either on time or late, so there would be two possibilities. If it met twice, the condition about what happens after two late arrivals in a row would never kick in, so all four combinations of (on time,on time), (on time,late), (late,on time), and (late,late) would be OK. And in fact, with only three classes in the semester there would be at most one class after two lates in a row, so again any sequence of three on time/late arrivals would be allowed, for eight possibilities. But what do we do for four or more classes, in which we have to start taking into account the special rule after two lates in a row?
The key lies in breaking down a longer semester into what happens initially and then what happens in the rest of the semester. To do that, let’s write `c_n` for the number of allowed sequences of arrival times in a semester consisting of `n` classes in all. Thus, we’ve figured out already that `c_1 = 2`, `c_2 = 4`, and `c_3 = 8`; the question is asking us for `c_{12}`. Now suppose the semester has `n` classes, where `n` is four or more. What might happen on the first class? If you’re on time, then that doesn’t put any restriction at all on what happens the rest of the semester — it could be anything that would be allowed in a semester that had only `n-1` classes. So that gives you `c_{n-1}` possible ways to finish out the semester. On the other hand, you might be late. What then? Well, if you’re late again immediately after that, then there are `n-2` classes left, and you can only be late in one of them, so you might be on time the rest of the semester (one possibility) or late on the first of those, or the second, or the third, …, or the last of those and on time for the rest of them (`n-2` possibilities). So there are `n-1` possible sequences in that case. And that leaves only the situation in which you are late, and then immediately redeem yourself by being on time at the next class. Now, you’re again in the situation that there are no restrictions on the rest of the semester, but now there are only `n-2` classes left, so there are `c_{n-2}` possibilities.
Since those are the only things that could happen to start off the semester, we know that `c_n = c_{n-1} + n − 1 + c_{n-2}`. While that does not (immediately) give you a specific formula for `c_n` in general, it’s now easy to calculate the desired `c_{12}` by repeated addition: `c_4 = 8 + 3 + 4 = 15`, `c_5=27`, `c_6=47`, `c_7=80`, `c_8=134`, `c_9=222`, `c_{10}=365`, `c_{11}=597`, and `c_{12}=`973.
Equations like this which relate one case of a general problem to one or more earlier or smaller cases of the same problem are known in the lingo as “recurrence relations”. A lot of times you’ll find they’re the hammer to you need to crack problems that seem like especially tough nuts. There are many problems that have no known formula for their solutions, but for which the answers can be found through the use of recurrence relations. So they’re a good technique to have in your bag of tricks.
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
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]
