Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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^(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>.
+
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 $n 2^{n-4} + 1$, as confirmed above. This claim can be verified by PIE: there are $n 2^{n-3}$ ways to arrange 3 adjacent chairs, but then we subtract $n 2^{n-4}$ 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 $\boxed{641}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_9&oldid=61248"