A certain performer tries to impress his audience by guessing the birthday date of a volunteer (previously unknown to him).
The volunteer is requested to multiply the numerical value of the month of his birth by 31, to multiply the numerical value of the day by 12, to add the two products and announce the result, say N.
Upon getting the result the performer, considerably quickly, deduces the MM/DD of the relevant birthdate.
a. Devise a way to quickly solve 12*d+31*m=N.
b. Show that there is a unique solution for any N, evaluated as described above.
I can't improve upon the analytic and computer solutions to part b already given.
For part a, start by computing N mod 12. The day part of the sum is always a multiple of 12 and so has no effect on the remainder.
If the month is even then m*31 = (m/2) * 62 = (m/2) * 2 mod 12 = m, so the remainder mod 12 is the month.
If the month is odd then m*31 = (m+1)/2 * 62 - 31 = (m+1)/2 * 2 - 7 mod 12 = m+1 - 7 mod 12 = m+1 + 5 mod 12 = m + 6 mod 12, so the remainder is 6 greater/less than the month.
Either way, if you know the remainder mod 12, it's easy to get the month. If your remainder is odd, you must add or subtract 6 (to stay positive), and if it's even, you're done. (And if it's zero, the month is December.)
From there you could certainly subtract 31*m from the original total, and then divide by 12 to get d. I'm not sure how quickly someone might be expected to do that in their head -- certainly it's more complex than computing the remainder mod 12, but it's still pretty simple arithmetic.
Let's try an example with today's date: August 19. N = 19*12 + 8*31 = 476.
N = 480 - 4 so N mod 12 = -4 = 8. Check.
31 * 8 = (30+1)*8 = 240 + 8 = 248.
476 - 248 = 228
228 / 12 = (120 +108) / 12 = 10 + 9 = 19. Check.
As an experiment, I asked one of my co-workers to "volunteer" and I tried this algorithm. I was successful, and I feel like it did indeed work fast enough, especially if it were combined with some patter or interaction with the volunteer. But I can't help but wonder if there is a further optimization to be had.
|
|
Posted by Paul
on 2016-08-19 17:52:14 |
part a
