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 "2018 AMC 10A Problems/Problem 4"

(→‎See Also)
(→‎Solution 1)
 
(25 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2018 AMC 10A Problems/Problem 4|2018 AMC 10A #4]] and [[2018 AMC 12A Problems/Problem 3|2018 AMC 12A #3]]}}
 +
 
==Problem==
 
==Problem==
  
−
How many ways can a student schedule 3 mathematics courses -- algebra, geometry, and number theory -- in a 6-period day if no two mathematics courses can be taken in consecutive periods? (What courses the student takes during the other 3 periods is of no concern here.)
+
How many ways can a student schedule <math>3</math> mathematics courses -- algebra, geometry, and number theory -- in a <math>6</math>-period day if no two mathematics courses can be taken in consecutive periods? (What courses the student takes during the other <math>3</math> periods is of no concern here.)
  
 
<math>\textbf{(A) }3\qquad\textbf{(B) }6\qquad\textbf{(C) }12\qquad\textbf{(D) }18\qquad\textbf{(E) }24</math>
 
<math>\textbf{(A) }3\qquad\textbf{(B) }6\qquad\textbf{(C) }12\qquad\textbf{(D) }18\qquad\textbf{(E) }24</math>
Line 12: Line 14:
  
 
Periods <math>1, 3, 5</math>
 
Periods <math>1, 3, 5</math>
 +
  
 
Periods <math>1, 3, 6</math>
 
Periods <math>1, 3, 6</math>
Line 19: Line 22:
 
Periods <math>2, 4, 6</math>
 
Periods <math>2, 4, 6</math>
  
−
There are <math>4</math> ways to place <math>3</math> nondistinguishable classes into <math>6</math> periods such that no two classes are in consecutive periods. For each of these ways, there are <math>3! = 6</math> orderings of the classes among themselves.
+
There are <math>4</math> ways to place <math>3</math> non distinguishable classes into <math>6</math> periods such that no two classes are in consecutive periods. For each of these ways, there are <math>3! = 6</math> orderings of the classes among themselves.
  
 
Therefore, there are <math>4 \cdot 6 = \boxed{\textbf{(E) } 24}</math> ways to choose the classes.
 
Therefore, there are <math>4 \cdot 6 = \boxed{\textbf{(E) } 24}</math> ways to choose the classes.
Line 26: Line 29:
  
 
==Solution 2==
 
==Solution 2==
−
Realize that the number of ways of placing, regardless of order, the 3 mathematics courses in a 6-period day so that no two are consecutive is the same as the number of ways of placing 3 mathematics courses in a sequence of 4 periods regardless of order and whether or not they are consecutive.
+
Counting what we don't want is another slick way to solve this problem. Use PIE (Principle of Inclusion and Exclusion) to count two cases: 1. Two classes consecutive, 2. Three classes consecutive.  
  
−
To see that there is a one to one correlation, note that for every way of placing 3 mathematics courses in 4 total periods (as above) one can add a non-mathematics course between each pair (2 total) of consecutively occurring mathematics courses (not necessarily back to back) to ensure there will be no two consecutive mathematics courses in the resulting 6-period day.
+
Case 1: Consider two consecutive periods as a "block" of which there are 5 places to put in(1,2; 2,3; 3,4; 4,5; 5,6). Then we simply need to place two classes within the block, <math>3 \cdot 2 </math>. Finally we have 4 periods remaining to place the final math class. Thus there are <math>5 \cdot 3 \cdot 2 \cdot 4</math> ways to place two consecutive math classes with disregard to the third.
−
For example, where <math>M</math> denotes a math course and <math>O</math> denotes a non-math course:
 
−
<math>M O M M \rightarrow M O O M O M</math>
 
  
−
For each 6-period sequence consisting of <math>M</math>s and <math>O</math>s, we have <math>3!</math> orderings of the 3 distinct mathematics courses.
+
Case 2: Now consider three consecutive periods as a "block" of which there are now 4 places to put in(1,2,3; 2,3,4; 3,4,5; 4,5,6). We now need to arrange the math classes in the block, <math>3 \cdot 2 \cdot 1</math>. Thus there are <math>4 \cdot 3 \cdot 2 \cdot 1</math> ways to place all three consecutive math classes.  
  
−
So, our answer is <math>\dbinom{4}{3}(3!)= \boxed{\textbf{(E) } 24}</math>
+
By PIE we subtract Case 1 by Case 2 in order to not overcount:  <math>120-24</math>. Then we subtract that answer from the total ways to place the classes with no restrictions: <math>(6 \cdot 5 \cdot 4) - 96= \boxed{\textbf{(E) } 24}</math>
  
−
- Gregwwl
+
-LitJamal
  
 
==Solution 3==
 
==Solution 3==
−
Counting what we don't want is another slick way to solve this problem. Use PIE to count two cases: 1. Two classes consecutive, 2. Three classes consecutive.  
+
We can tackle this problem with a stars-and-bars-ish approach. First, letting math class be 1 and non-math-class be 0, place 0s in between 3 1s:
 +
<cmath>10101</cmath>
 +
Now we need to place 1 additional 0. There are 4 places to put it: <cmath>\underline{\hspace{0.3cm}}1\underline{\hspace{0.3cm}}01\underline{\hspace{0.3cm}}01\underline{\hspace{0.3cm}}</cmath> It can be placed in any 1 of the underscores.
 +
Since there are <math>3!=6</math> ways to order the math classes, the answer is <math>6\cdot 4=\boxed{\textbf{(E) } 24}</math>.
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Firebolt360 firebolt360]
 +
 
 +
==Solution 4==
 +
Let <math>M</math> represent a math class and <math>N</math> represent a non-math class. We have _N_N_N_, where the spaces represent the possible spots the <math>M’s</math> could go in. There are <math>4\choose 3</math> ways to choose the spots for the math classes and <math>3!=6</math> ways to order the classes. Hence, the answer is <math>4 \cdot 6 = \boxed{\textbf{(E) } 24}</math>.
 +
~azc1027
 +
 
 +
==Video Solution (CREATIVE THINKING!)==
 +
https://youtu.be/GHCecqsF8es
 +
 
 +
Education, the Study of Everything
  
−
Case 1: Consider two consecutive periods as a "block" of which there are 5 places to put in(1,2; 2,3; 3,4; 4,5; 5,6). Then we simply need to place two classes within the block, <math>3 \cdot 2 </math>. Finally we have 4 periods remaining to place the final math class. Thus there are <math>5 \cdot 3 \cdot 2 \cdot 4</math> ways to place two consecutive math classes with disregard to the third.
+
==Video Solution==
 +
https://youtu.be/vO-ELYmgRI8
  
−
Case 2: Now consider three consecutive periods as a "block" of which there are now 4 places to put in(1,2,3; 2,3,4; 3,4,5; 4,5,6). We now need to arrange the math classes in the block, <math>3 \cdot 2 \cdot 1</math>. Thus there are <math>4 \cdot 3 \cdot 2 \cdot 1</math> ways to place all three consecutive math classes.
+
~IceMatrix
  
−
By PIE we subtract Case 1 by Case 2 in order to not overcount: <math>120-24</math>. Then we subtract that answer from the total ways to place the classes with no restrictions: <math>(6 \cdot 5 \cdot 4) - 96= \boxed{\textbf{(E) } 24}</math>
+
==Video Solution==
 +
https://youtu.be/kBOCP8p8-o8
  
−
-LitJamal
+
~savannahsolver
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2018|ab=A|num-b=3|num-a=5}}
 
{{AMC10 box|year=2018|ab=A|num-b=3|num-a=5}}
 +
{{AMC12 box|year=2018|ab=A|num-b=2|num-a=4}}
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
[[Category:Introductory Combinatorics Problems]]
 
[[Category:Introductory Combinatorics Problems]]

Latest revision as of 21:59, 22 October 2024

The following problem is from both the 2018 AMC 10A #4 and 2018 AMC 12A #3, so both problems redirect to this page.

Problem

How many ways can a student schedule $3$ mathematics courses -- algebra, geometry, and number theory -- in a $6$-period day if no two mathematics courses can be taken in consecutive periods? (What courses the student takes during the other $3$ periods is of no concern here.)

$\textbf{(A) }3\qquad\textbf{(B) }6\qquad\textbf{(C) }12\qquad\textbf{(D) }18\qquad\textbf{(E) }24$

Solution 1

We must place the classes into the periods such that no two classes are in the same period or in consecutive periods.

Ignoring distinguishability, we can thus list out the ways that three periods can be chosen for the classes when periods cannot be consecutive:

Periods $1, 3, 5$


Periods $1, 3, 6$

Periods $1, 4, 6$

Periods $2, 4, 6$

There are $4$ ways to place $3$ non distinguishable classes into $6$ periods such that no two classes are in consecutive periods. For each of these ways, there are $3! = 6$ orderings of the classes among themselves.

Therefore, there are $4 \cdot 6 = \boxed{\textbf{(E) } 24}$ ways to choose the classes.

-Versailles15625

Solution 2

Counting what we don't want is another slick way to solve this problem. Use PIE (Principle of Inclusion and Exclusion) to count two cases: 1. Two classes consecutive, 2. Three classes consecutive.

Case 1: Consider two consecutive periods as a "block" of which there are 5 places to put in(1,2; 2,3; 3,4; 4,5; 5,6). Then we simply need to place two classes within the block, $3 \cdot 2$. Finally we have 4 periods remaining to place the final math class. Thus there are $5 \cdot 3 \cdot 2 \cdot 4$ ways to place two consecutive math classes with disregard to the third.

Case 2: Now consider three consecutive periods as a "block" of which there are now 4 places to put in(1,2,3; 2,3,4; 3,4,5; 4,5,6). We now need to arrange the math classes in the block, $3 \cdot 2 \cdot 1$. Thus there are $4 \cdot 3 \cdot 2 \cdot 1$ ways to place all three consecutive math classes.

By PIE we subtract Case 1 by Case 2 in order to not overcount: $120-24$. Then we subtract that answer from the total ways to place the classes with no restrictions: $(6 \cdot 5 \cdot 4) - 96= \boxed{\textbf{(E) } 24}$

-LitJamal

Solution 3

We can tackle this problem with a stars-and-bars-ish approach. First, letting math class be 1 and non-math-class be 0, place 0s in between 3 1s: \[10101\] Now we need to place 1 additional 0. There are 4 places to put it: \[\underline{\hspace{0.3cm}}1\underline{\hspace{0.3cm}}01\underline{\hspace{0.3cm}}01\underline{\hspace{0.3cm}}\] It can be placed in any 1 of the underscores. Since there are $3!=6$ ways to order the math classes, the answer is $6\cdot 4=\boxed{\textbf{(E) } 24}$.

~firebolt360

Solution 4

Let $M$ represent a math class and $N$ represent a non-math class. We have _N_N_N_, where the spaces represent the possible spots the $M’s$ could go in. There are $4\choose 3$ ways to choose the spots for the math classes and $3!=6$ ways to order the classes. Hence, the answer is $4 \cdot 6 = \boxed{\textbf{(E) } 24}$. ~azc1027

Video Solution (CREATIVE THINKING!)

https://youtu.be/GHCecqsF8es

Education, the Study of Everything

Video Solution

https://youtu.be/vO-ELYmgRI8

~IceMatrix

Video Solution

https://youtu.be/kBOCP8p8-o8

~savannahsolver

See Also

2018 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2018 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2018_AMC_10A_Problems/Problem_4&oldid=230379"