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"

(→‎Solution 3 (Complementary Counting))
m (→‎Solution 1 (Casework))
Line 3: Line 3:
  
 
==Solution 1 (Casework)==
 
==Solution 1 (Casework)==
−
We know that a subset with less than <math>3</math> chairs cannot contain <math>3</math> adjacent chairs.  There are only <math>10</math> sets of <math>3</math> chairs so that they are all <math>3</math> adjacent.  There are <math>10</math> subsets of <math>4</math> chairs where all <math>4</math> are adjacent, and <math>10 * 5</math> or <math>50</math> where there are only <math>3.</math>  If there are <math>5</math> chairs, <math>10</math> have all <math>5</math> adjacent, <math>10 * 4</math> or <math>40</math> have <math>4</math> adjacent, and <math>10 * {5\choose 2}</math> or <math>100</math> have <math>3</math> adjacent.  With <math>6</math> chairs in the subset, <math>10</math> have all <math>6</math> adjacent, <math>10(3)</math> or <math>30</math> have <math>5</math> adjacent, <math>10 * {4\choose2}</math> or <math>60</math> have <math>4</math> adjacent, <math>\frac{10 * 3}{2}</math> or <math>15</math> have <math>2</math> groups of <math>3</math> adjacent chairs, and <math>10 * ({5\choose2} - 3)</math> or <math>70</math> have <math>1</math> group of <math>3</math> adjacent chairs.  All possible subsets with more than <math>6</math> chairs have at least <math>1</math> group of <math>3</math> adjacent chairs, so we add <math>{10\choose7}</math> or <math>120</math>, <math>{10\choose8}</math> or <math>45</math>, <math>{10\choose9}</math> or <math>10</math>, and <math>{10\choose10}</math> or <math>1.</math>  Adding, we get <math>10 + 10 + 50 + 10 + 40 + 100 + 10 + 30 + 60 + 15 + 70 + 120 + 45 + 10 + 1 = \boxed{581}.</math>
+
We know that a subset with less than <math>3</math> chairs cannot contain <math>3</math> adjacent chairs.  There are only <math>10</math> sets of <math>3</math> chairs so that they are all <math>3</math> adjacent.  There are <math>10</math> subsets of <math>4</math> chairs where all <math>4</math> are adjacent, and <math>10 * 5</math> or <math>50</math> where there are only <math>3.</math>  If there are <math>5</math> chairs, <math>10</math> have all <math>5</math> adjacent, <math>10 * 4</math> or <math>40</math> have <math>4</math> adjacent, and <math>10 * {5\choose 2}</math> or <math>100</math> have <math>3</math> adjacent.  With <math>6</math> chairs in the subset, <math>10</math> have all <math>6</math> adjacent, <math>10(3)</math> or <math>30</math> have <math>5</math> adjacent, <math>10 * {4\choose2}</math> or <math>60</math> have <math>4</math> adjacent, <math>\frac{10 * 3}{2}</math> or <math>15</math> have <math>2</math> groups of <math>3</math> adjacent chairs, and <math>10 * ({5\choose2} - 3)</math> or <math>70</math> have <math>1</math> group of <math>3</math> adjacent chairs.  All possible subsets with more than <math>6</math> chairs have at least <math>1</math> group of <math>3</math> adjacent chairs, so we add <math>{10\choose7}</math> or <math>120</math>, <math>{10\choose8}</math> or <math>45</math>, <math>{10\choose9}</math> or <math>10</math>, and <math>{10\choose10}</math> or <math>1.</math>  Adding, we get <math>10 + (10 + 50) + (10 + 40 + 100) + (10 + 30 + 60 + 15 + 70) + 120 + 45 + 10 + 1 = \boxed{581}.</math>
  
 
==Solution 2 (PIE)==
 
==Solution 2 (PIE)==

Revision as of 23:32, 11 July 2015

Problem

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Solution 1 (Casework)

We know that a subset with less than $3$ chairs cannot contain $3$ adjacent chairs. There are only $10$ sets of $3$ chairs so that they are all $3$ adjacent. There are $10$ subsets of $4$ chairs where all $4$ are adjacent, and $10 * 5$ or $50$ where there are only $3.$ If there are $5$ chairs, $10$ have all $5$ adjacent, $10 * 4$ or $40$ have $4$ adjacent, and $10 * {5\choose 2}$ or $100$ have $3$ adjacent. With $6$ chairs in the subset, $10$ have all $6$ adjacent, $10(3)$ or $30$ have $5$ adjacent, $10 * {4\choose2}$ or $60$ have $4$ adjacent, $\frac{10 * 3}{2}$ or $15$ have $2$ groups of $3$ adjacent chairs, and $10 * ({5\choose2} - 3)$ or $70$ have $1$ group of $3$ adjacent chairs. All possible subsets with more than $6$ chairs have at least $1$ group of $3$ adjacent chairs, so we add ${10\choose7}$ or $120$, ${10\choose8}$ or $45$, ${10\choose9}$ or $10$, and ${10\choose10}$ or $1.$ Adding, we get $10 + (10 + 50) + (10 + 40 + 100) + (10 + 30 + 60 + 15 + 70) + 120 + 45 + 10 + 1 = \boxed{581}.$

Solution 2 (PIE)

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, n chairs should give $n 2^{n-4} + 1$, as confirmed above. This claim can be verified by the principle of inclusion-exclusion: 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 the full subset of chairs. Thus, for $n = 10$ we get a first count of $641.$

However, we overcount cases in which there are two distinct groups of three or more chairs. Time to casework: we have $5$ cases for two groups of $3$ directly opposite each other, $5$ for two groups of four, $20$ for two groups of $3$ not symmetrically opposite, $20$ for a group of $3$ and a group of $4$, and $10$ for a group of $3$ and a group of $5.$ Thus, we have $641 - 60 = \boxed{581}$.

See also

2014 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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