“A purse contains 4 Pennies, 2 Nickels, 1 Dime and 1 Quarter. How many different values can be obtained using one or more coins from the purse?”
This poser came by mail today morning, a time when I am at my best. Its main appeal was it did not involve conditional probabilities or 3D geometry. Just the kind I am known (to myself) to crack in no time.
The wheels whirred and this was how:
4 Pennies can be used as no Penny, one Penny, two Pennies, 3 Pennies and 4 Pennies. In five different ways.
2 Nickels in three different ways: no Nickel, one Nickel and two nickels.
1 Dime in two different ways: no Dime, one Dime.
Similarly a Quarter In two different ways: no Quarter and one Quarter.
So the total number of ways these coins could be drawn from the purse was the combination of 5, 3, 2 and 2 = 60 different ways. I remembered I should reduce the count by one to eliminate the instance of not drawing any coin at all.
Beset with the afterglow that usually comes with living up to one’s reputation, I was all set to announce to my mother it is cracked – she was the only one nearby.
Just then the term ‘different values’ struck me. In my scheme of things, drawing only 2 Nickels and drawing only one Dime were two different instances of those 59 but yielding the same value.
So my method was flawed. I need to find those duplicate instances giving the same value and reduce them from the overall count. And how does one go about?
Well, there ought to be a different approach.
A second look at the problem revealed a base-5 number system in use. In the units place, there was this Penny. At five’s place, it was the Nickel and at the twenty-five’s place there was this Quarter. With the available coins I could go single-stepping all the way to 4*5’0 + 2*5’1 + 1*5’2 = 39.
There is still a Dime to account for. That part was easy. The Dime gave me the facility of an offset of 10 cents. Now I could draw any amount from 1 to 49 cents.
Going over it once more, it was foolproof.
Now there was no holding back. I proudly announced it to my mother. She listened to the problem statement carefully.
‘What’s the big thing about it? Get the coins and count them – there are not too many coins, it should be quite manageable.’
I explained to her patiently it is not the solution itself but the method of solving that is important as it allows one to scalably solve a whole class of similar problems and that’s what I went after.
I can’t say how much of it went to her. But she said loudly, ‘Hey, listen you all. Didn’t I say my son is brilliant?’
The house continued its silence.
Nevertheless I’m pleased with myself.
The zillion other things piled up for me by life and my wife can wait including cleaning up family’s meagre finances.
And what if this poser was one faced by my 9-year old granddaughter in a Math Olympiad. I learnt she got it just like that. Am I glad I’m no longer required to measure up to these kids.
I’m still pleased with myself.