On New Years Day, Penny resolved to make poverty history.

Unfortunately Penny was penniless and asking her relatives for cash seemed a bit passe, so she asked them to contribute goats.

Frankie, Mark, Dolly, Squidly, Ruby and Draco each sent goat vouchers. Each of the vouchers was for a three figure number of goats. Penny was delighted with the response, over 5200 goats in total. Even better, she found that after using 11 of the goats to pay local administrative expenses, each of the beneficiaries would receive exactly 32 goats.

Curiously she noticed that the each of the donations was the product of exactly six prime numbers. If Frankie gave more than Mark, who gave more than Dolly, who gave more than Squidly, who gave more than Ruby, who gave more than Draco, how many did each give?

The computer solultion is probably more elegant, but here's one done by hand.

First, we'll need all the three digit numbers that are the product of exactly six primes. I'm going to group them by the number of times 2 is a factor. They are: 2^5*{2 - 31} (where {} means pick any one prime number in the range, inclusive), 2^4*3*{3-19}, 2^4*5*{5-11}, 2^4*7^2, 2^3*3^2*{3-13}, 2^3*3*5*{5-7}, 2^2*3^3*{3-7}, 2^2*3^2*5^2, 2*3^4*{3-5}, and 3^6.

Since the goats were divided evenly among 32 recipients after 11 were used as an administrative fee, the total number of goats N = 11 mod 32. Specifically, N = 32*k + 11 and so is ODD. But only one of the possible numbers above is odd -- the only one without a factor of 2. So one of the numbers is 3^6=729. 729 is 25 mod 32, and so the remaining numbers collectively must be 18 mod 32 in order to  have the total be 11 mod 32.

All of the numbers with two or more 2's will be multiples of 4 mod 32, and so will their sum. So to reach a total of 18 there must be an odd number of numbers with exactly one factor of 2. Since there are only two such numbers, exactly one of them must be used. But using the smaller (486) would mean that the remaining four totals would have to sum to at least 3985 for the grand total to be at least 5200. A quick check shows that the four largest numbers are insufficient, which rules out 486, requiring that 2*3^4*5=810 be one of the vouchers. Since the sum of these first two numbers is 3 mod 32, the remaining four numbers must total 8 mod 32.

We can get a total of 8 mod 32 either by two numbers that are 4 mod 32 or by one number that's 8 mod 32 included in the sum. But suppose even the two largest 4mod32 numbers (900 and 756) were chosen. The first four numbers would total 3195 and so it would be impossible to reach 5200 with two 3-digit numbers. So there must be exactly one number with exactly three factors of 2 on the list. Any number less than 662 would require a 4-digit number among the last three to reach 5200 so there are only three feasible choices: 792, 840, and 936.

Consider each choice in turn. If 792 were the third number, then the running total would be equal to 27 mod 32 and either one or all three of the final numbers would have to be 16mod32 in order for the grand total to be 11 mod 32. Now, the three largest choices that are 16mod32 are 912, 880, and 816, and if all three were used with 792 the grand total would be only 4939 -- too short. And if the single larges were used along with the two largest 32mod32 numbers (992 and 928) that total would be 5163 -- still too short. Axe 792. Using 840 or 936 means the running total is already 11mod32 and so either zero or two of the final numbers are 16mod32. The three largest 32mod32 numbers are 992,928, and 736, so if there are zero 16's even choosing 936 gives a total of only 5131, so there must be two 16's and one 32mod32. The largest we can hope for for this combination is (912+880)+992 which combined with the first two numbers is 4323. If our fourth number is 840, the grand total is only 5163--too small--but if we select 936 then the total is 5259 -- success!


So, that makes the whole set of six (now placed in descending order) 992, 936, 912, 880, 810, and 729 for a grand total of 5259 goats. These are then the values that Frankie, Mark, Dolly, Squidly, Ruby, and Draco gave, respectively. As a test, 5259-11=5248=32*164.

All things considered, it's quicker to type the computer program than this explanation!

Posted by Paul on 2006-02-24 00:36:31