Wednesday, August 17, 2011

Are you smarter than a 6th grader?

This problem was proposed to a math olympiad for 6th graders. The solution doesn't require any algebra nor any more advanced tools, other than simply logic.


Each apple costs 1 dollar and each orange costs 1.01 dollar. Johnny has 101 dollars. How many ways are there for him to buy fruits, including possibly not buying anything? Sarah has 99 dollars. How many ways are there for her to buy fruits, including possibly not buying anything?


First we make an observation that 100 and 101 are relatively prime. So suppose Johnny buys X apples and Y oranges and spends exactly Z amount of money. If he wants to spend EXACTLY Z amount of money with a different combination of fruits, he would have to decrease X by 101 and increase Y by 100, or increase X by 101 and decrease Y by 100.

For Johnny,

Consider case 1: If Johnny spends exactly 101 dollars. Clearly he can buy 101 apples or 100 oranges, but these are the only two cases.

Case 2: If Johnny spends less than 101 dollars. Now, pretend that the store only has 101 apples and 100 oranges (since Johnny can’t buy more apples or more oranges than these).

Consider all the combinations of apples and oranges that Johnny can buy, and consider what’s left at the store. The total amount of goods in the store are 1 dollar x 101 + 1.01 dollar x 100 = 202 dollars. So if Johnny spends less than 101 dollars, the total amount goods left in the store is greater than 101 dollars. We can’t reverse this situation, that is, Johnny can never spend more than 101 dollars so that the total amount left in the store is less than 101 dollars.

This means, in all the possible combinations of x apples (x is from 0 to 101 inclusive) and y oranges (from 0 to 100 inclusive), for each combination that Johnny can buy, there is precisely one combination that Johnny couldn’t buy. The combinations that Johnny couldn’t buy represent the amount that would be left in the store if Johnny had bought the “complement” combination instead.

The total number of combinations is 102 x 101 = 10302, (because we go from 0 apples to 101 inclusive, 0 oranges to 100 inclusive) but we have to subtract two combinations from case 1, so we have 10 300, split evenly between what Johnny could buy and couldn’t buy. So Johnny could buy 5150 combinations.

Together from Case 1 and Case 2, Johnny could buy fruits in 5152 ways.

For Sarah,

Case 1: She spends exactly 99 dollars. She can buy 99 apples. She couldn’t buy any oranges because if she wants to buy any oranges she’d have to increase it in increments of 100 and decrease the apples in increments of 101, again because 101 and 100 are relatively prime.

Now, consider the story of Johnny. Out of 5150 ways he could buy fruits, categorize them according to his spending:
Category 1: He spends 0 to 98.99
Category 2: He spends 99 exactly
Category 3: He spends 99.01 to 100.99
Category 4: He spends 101

Suppose he buys a certain number of apples and oranges. In order to keep the spending amount intact and changes the number of apples or oranges, as we’ve noted above, he would have to change the number of apples and oranges in increments of 101 and 100 respectively. The total amount of goods being changes (from apples to oranges or vice versa) is already 101 dollars. This is why in category 4 he has two ways of buying good. But this means, in category 1, 2, and 3, for each spending amount, there’s at most one (possibly zero) way to buy fruits with that spending amount.

Now, we show that 98.99 dollars spending amount is unattainable. Johnny could achieve that amount by buying 100 apples and –1 oranges, or –1 apples and 99 oranges. Neither one are reasonable.

Next, for each amount in category 1, we pair them up. We pair up X with 98.99 – X. For example, 0 and 98.99 is paired up. 0.01 and 98.98 is paired up, etc.

We claim that within each pair, at most one value is attainable, possibly zero. If both values are attainable, say if Johnny could buy A apples and B oranges with X dollars and C apples and D oranges with 98.99 – X dollars, then he could buy (A+C) apples and (B+D) oranges with 98.99 dollars, a contradiction since we’ve shown that 98.99 is unattainable. So since there are 9900 values, and thus 4950 pairs of values, so there are at most 4950 ways to buy fruits in category 1.

But then there is 1 way in category 2, and total of 5150 ways in category 1,2,3 altogether. So there are at least (5150 – 1 – 4950) = 199 ways to buy in category 3. But notice that there are exactly 199 values (amounts) in category 3, each of which can correspond to at most one way to buy fruits. Thus we must have that each value in category 3 is attainable by exactly one way of buying, and each pair of values in category 1 is attainable by exactly one way of buying.

So in total, when Sarah spends her money, she can spend it from category 1 or 2, and there are 4950 + 1 = 4951 ways of buying.

Sunday, August 14, 2011

General Recursion

Given a recursive formula with $a_{n+1} = 2a_n -1$ and $a_1 = a$, find a general formula for $a_n$.