# Difference between revisions of "2014 AIME II Problems/Problem 9"

(Created page with "==Solution== Starting with small cases, we see that four chairs give 4 + 1 = 5, five chairs give 5 + 5 + 1 = 11, and six chairs give 6 + 6 + 6 + 6 + 1 = 25. Thus, I claim that n ...") |
(→Solution) |
||

Line 1: | Line 1: | ||

==Solution== | ==Solution== | ||

− | Starting with small cases, we see that four chairs give 4 + 1 = 5, five chairs give 5 + 5 + 1 = 11, and six chairs give 6 + 6 + 6 + 6 + 1 = 25. Thus, I claim that n chairs give <math>n 2^{n-4} + 1</math>, as confirmed above. This claim can be verified by PIE: there are <math>n 2^ | + | Starting with small cases, we see that four chairs give 4 + 1 = 5, five chairs give 5 + 5 + 1 = 11, and six chairs give 6 + 6 + 6 + 6 + 1 = 25. Thus, I claim that n chairs give <math>n 2^{n-4} + 1</math>, as confirmed above. This claim can be verified by PIE: there are <math>n 2^{n-3}</math> ways to arrange 3 adjacent chairs, but then we subtract <math>n 2^{n-4}</math> ways to arrange 4. Finally, we add 1 to account for all chairs case (the other cases have been taken care of). Thus, for n = 10 we get <math>\boxed{641}</math>. |

## Revision as of 17:18, 28 March 2014

## Solution

Starting with small cases, we see that four chairs give 4 + 1 = 5, five chairs give 5 + 5 + 1 = 11, and six chairs give 6 + 6 + 6 + 6 + 1 = 25. Thus, I claim that n chairs give , as confirmed above. This claim can be verified by PIE: there are ways to arrange 3 adjacent chairs, but then we subtract ways to arrange 4. Finally, we add 1 to account for all chairs case (the other cases have been taken care of). Thus, for n = 10 we get .