Susan gave her nephew a number of pennies, as well as a mathematical challenge: to figure out how many ways there were of dividing the pennies into three piles. The pennies are indistinguishable, so the identity of the pennies doesn't matter, nor does the order of the piles. For example, if there had been nine pennies, the piles could have been arranged in any of seven ways: 1+1+7, 1+2+6, 1+3+5, 1+4+4, 2+2+5, 2+3+4, 3+3+3.

There were actually more pennies than this, and in fact, the number of ways was a four-digit number.

However, the nephew misunderstood the instructions. He thought that no two of the piles could be equal, and so came up with a smaller number. For example, if the number of pennies were nine, as above, only three of the arrangements into piles consisted of unique sizes: 1+2+6, 1+3+5, 2+3+4, and the nephew would have reported that, incorrectly.

As mentioned the actual number of ways was a four-digit number. The number reported by the nephew was also a four-digit number, and as a result of his misunderstanding, the only difference between his reported number and Susan's expected answer was that the middle two digits were reversed.

How many pennies did Susan give to her nephew?

The number of partitions into J piles can be calculated by using a recursion relation to express it in terms of the number of partitions of J-1 piles.

The two pile case is very simple. The number of ways to write K = A + B with A >= B is just Int(K/2), where Int indicates the greatest integer less than or equal to the argument.

Write M(3,K) = #of partitions of K objects into 3 piles, then we have already seen that M(2,K) = Int(K/2). Now our recursion relation is

M(3,K) = M(2,K-3) + M(2,K-6) +..+ M(2,K-3LM)  + L

L = Int( K/3 )

here the term in K-3L is formed by notionally removing L coins into pile 1, then calculating the number of ways to split the remaining K-L coins between the other two piles subject to the constraint that each of the other piles is apportioned at least L coins as well.

The (underlined) constraint above ensures that we conform to the instruction of neglecting the order of the piles. This mimics the problem examples, in which pile 3 has at least as many coins as pile 2, etc. So, if we know that there are L coins in pile 1, we can start with a partial allocation of the same number to the other two piles. We are then left with enumerating the number of ways to partion the remaining coins, namely K-3L, between the second and third pile. Finally the Int(K/3) term appears because each M(2,X) term underestimates the number of relevant partitions by 1. (This is easily seen by considering the three coin case, for instance.) The final term in the series occurs for L = Int(K/3). 

It is convenient to reorder the terms of the recurrence relation:

M(3,K) = [ M(2,K-3) + M(2,K-9) +..+ M(2,K+3-6U) ]

          + [ M[2,K-6] + M[2,K-12) +..+ M(2,K-6V) ] + Int(K/3)

          = Ma + Mb + Int(K/3)

Then  Ma = UM(2,K-3) - 3 (1+..+U-1) = UM(2,K-3) - 3U(U-1)/2

where  U = Int( (K+3)/6 )   Similarly

Mb = VM(2,K-6) - 3V(V-1)/2   with  V = Int( K/6 ) 

Now it is useful to turn to the number of partition according to the constraint introduced by the nephew's understanding. We denote this N(J,K), and discover that many of our previous results are applicable. In fact, each of the nephews partitions may be identified with an aunt type partition by first allocating (B,B+1,B+2) coins amongst the three piles, then distributing the remaining coins between the second and third piles according to the aunt's constraint definition. Hence 

N(3,K) = M(2,K-6) + M(2,K-9) +..+ M(2,K-3L) + Int( (K-3)/3 ) = M(3,K-3)

This gives us the material we need to solve the problem. Before proceeding further though we note that none of the results obtained so far appears connected with a reversal of digits. In fact, my strong suspicion is that there is no such connection, and nothing to be learnt by trying to derive an equation giving K based on this condition. I therefore felt justified to move forward by modelling the M formula in a table, assigning Excel the task of identifying solution(s).

There are 237 values of K which lead to a four digit M value (from K=110 to K=346). Of these, there are 26 values of K for which we can find a K1 such that M(K) = r(N(K1)), where r reverses the second and third digits of its argument. However there is only one value of K which gives K1(K) = K, and that is K = 182: for 182 coins the aunt calculates M(182) = 2760 while the nephew calculates N(182) = M(179) = 2670.

Edited on April 11, 2008, 3:35 pm

Posted by FrankM on 2008-04-10 21:36:40