Difference between revisions of "2015 AMC 10A Problems/Problem 22"

m (Solution 5)
m (Solution 5 (Recursion))
(23 intermediate revisions by 13 users not shown)
Line 6: Line 6:
 
<math>\textbf{(A)}\dfrac{47}{256}\qquad\textbf{(B)}\dfrac{3}{16}\qquad\textbf{(C) }\dfrac{49}{256}\qquad\textbf{(D) }\dfrac{25}{128}\qquad\textbf{(E) }\dfrac{51}{256} </math>
 
<math>\textbf{(A)}\dfrac{47}{256}\qquad\textbf{(B)}\dfrac{3}{16}\qquad\textbf{(C) }\dfrac{49}{256}\qquad\textbf{(D) }\dfrac{25}{128}\qquad\textbf{(E) }\dfrac{51}{256} </math>
  
==Solution==
 
===Solution 1===
 
We count how many valid arrangements there are and then divide by <math>2^8=256</math>.
 
  
First, arbitrarily pick a person A and consider whether he is standing or sitting.
 
If he is sitting, then the number of valid arrangements is the same as the number of valid arrangements of 7 people in a line.
 
If he is standing, then the two people next to him must be sitting, so the number of valid arrangements is the same as the number of valid arrangements of 5 people in a line.
 
  
Let <math>a_n</math> denote the number of ways to arrange <math>n</math> people in a line such that no two adjacent people are standing. We determine a recurrence relation for <math>a_n,\ n\geq 2</math> as follows. If the first person in the line is standing, then the next person must be sitting, and there are <math>a_{n-2}</math> ways to arrange the rest. If the first person in the line is sitting, then there are <math>a_{n-1}</math> ways to arrange the rest. Thus, <math>a_n=a_{n-1}+a_{n-2}</math> and using the fact that <math>a_0=1</math> and <math>a_1=2</math>, we get that <math>a_n</math> is the <math>(n+2)</math>nd Fibonacci number <math>F_{n+2}</math>. In particular, <math>a_5=F_7=13</math> and <math>a_7=F_9=34</math>.
+
==Solution 1==
 
 
So our desired count is <math>a_7+a_5=34+13=47</math>, and the answer is <math>\boxed{\textbf{(A) } \frac{47}{256}}</math>.
 
 
 
===Solution 2===
 
 
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by <math>2^8 = 256</math> at the end. We casework on how many people are standing.
 
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by <math>2^8 = 256</math> at the end. We casework on how many people are standing.
  
Line 27: Line 17:
 
Case <math>3:</math> <math>2</math> people are standing. This yields <math>\dbinom{8}{2} - 8 = 20</math> arrangements, because the two people cannot be next to each other.
 
Case <math>3:</math> <math>2</math> people are standing. This yields <math>\dbinom{8}{2} - 8 = 20</math> arrangements, because the two people cannot be next to each other.
  
Case <math>4:</math> <math>4</math> people are standing. Then the people must be arranged in stand-sit-stand-sit-stand-sit-stand-sit fashion, yielding <math>2</math> possible arrangements.
+
Case <math>5:</math> <math>4</math> people are standing. Then the people must be arranged in stand-sit-stand-sit-stand-sit-stand-sit fashion, yielding <math>2</math> possible arrangements.
  
 
More difficult is:
 
More difficult is:
  
Case <math>5:</math> <math>3</math> people are standing. First, choose the location of the first person standing (<math>8</math> choices). Next, choose <math>2</math> of the remaining people in the remaining <math>5</math> legal seats to stand, amounting to <math>6</math> arrangements considering that these two people cannot stand next to each other. However, we have to divide by <math>3,</math> because there are <math>3</math> ways to choose the first person given any three. This yields <math>\dfrac{8 \cdot 6}{3} = 16</math> arrangements for Case <math>5.</math>
+
Case <math>4:</math> <math>3</math> people are standing. First, choose the location of the first person standing (<math>8</math> choices). Next, choose <math>2</math> of the remaining people in the remaining <math>5</math> legal seats to stand, amounting to <math>6</math> arrangements considering that these two people cannot stand next to each other. However, we have to divide by <math>3,</math> because there are <math>3</math> ways to choose the first person given any three. This yields <math>\dfrac{8 \cdot 6}{3} = 16</math> arrangements for Case <math>5.</math>
  
Alternate Case <math>5:</math> Use complementary counting. Total number of ways to choose 3 people from 8 which is <math>\dbinom{8}{3}</math>. Sub-case <math>1:</math> three people are next to each other which is <math>\dbinom{8}{1}</math>. Sub-case <math>2:</math> two people are next to each other and the third person is not <math>\dbinom{8}{1}</math> <math>\dbinom{4}{1}</math>. This yields <math>\dbinom{8}{3} - \dbinom{8}{1} - \dbinom{8}{1} \dbinom{4}{1} = 16</math>  
+
Alternate Case <math>4:</math> Use complementary counting. Total number of ways to choose 3 people from 8 which is <math>\dbinom{8}{3}</math>. Sub-case <math>1:</math> three people are next to each other which is <math>\dbinom{8}{1}</math>. Sub-case <math>2:</math> two people are next to each other and the third person is not <math>\dbinom{8}{1}</math> <math>\dbinom{4}{1}</math>. This yields <math>\dbinom{8}{3} - \dbinom{8}{1} - \dbinom{8}{1} \dbinom{4}{1} = 16</math>  
  
 
Summing gives <math>1 + 8 + 20 + 2 + 16 = 47,</math> and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
 
Summing gives <math>1 + 8 + 20 + 2 + 16 = 47,</math> and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
  
===Solution 3===
+
Alternate: (Quicksolve) - We know that for case 5, there are 8 ways to choose the first person, and 3 ways to choose the first person given any 3 - which means that for the case, there is 8 * something divided by 3. The sum of the other cases is 31/256. Thus, add a multiple of 8 to 31 to get an answer. The options are 31 + 8 = 39, 31 + 16 = 47, 31 + 24 = 55, etc. The only possible answer is 47/256.
 +
 
 +
==Solution 2==
 
We will count how many valid standing arrangements there are counting rotations as distinct and divide by <math>256</math> at the end.
 
We will count how many valid standing arrangements there are counting rotations as distinct and divide by <math>256</math> at the end.
 
Line up all <math>8</math> people linearly.  In order for no two people standing to be adjacent, we will place a sitting person to the right of each standing person.  In effect, each standing person requires <math>2</math> spaces and the standing people are separated by sitting people.  We just need to determine the number of combinations of pairs and singles and the problem becomes very similar to pirates and gold aka stars and bars aka sticks and stones aka balls and urns.
 
Line up all <math>8</math> people linearly.  In order for no two people standing to be adjacent, we will place a sitting person to the right of each standing person.  In effect, each standing person requires <math>2</math> spaces and the standing people are separated by sitting people.  We just need to determine the number of combinations of pairs and singles and the problem becomes very similar to pirates and gold aka stars and bars aka sticks and stones aka balls and urns.
Line 51: Line 43:
 
Together we have <math>34+13=47</math>, and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
 
Together we have <math>34+13=47</math>, and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
  
===Solution 4===
+
== Solution 3 (Recursion) ==
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by <math>2^8 = 256</math> at the end. If we suppose for the moment that the people are in a line, and decide from left to right whether they sit or stand. If the leftmost person sits, we have the same number of arrangements as if there were only <math>7</math> people. If they stand, we count the arrangements with <math>6</math> instead because the person second from the left must sit. We notice that this is the Fibonacci sequence, where with <math>1</math> person there are two ways and with <math>2</math> people there are three ways. Carrying out the Fibonacci recursion until we get to <math>8</math> people, we find there are <math>55</math> standing arrangements. Some of these were illegal however, since both the first and last people stood. In these cases, both the leftmost and rightmost two people are fixed, leaving us to subtract the number of ways for <math>4</math> people to stand in a line, which is <math>8</math> from our sequence. Therefore our probability is <math>\frac{55 - 8}{256} = \boxed{\textbf{(A) } \dfrac{47}{256}}</math>
+
Because the denominator is always <math>256</math>, we can count the numerator with a recursion. Define <math>c_n</math> and <math>r_n</math> as the number of satisfying arrangements on a circle and row with <math>n</math> seats, respectively.
 +
 
 +
Then, observe that <cmath>c_n=r_{n-1}+r_{n-3}</cmath> <cmath>r_n=r_{n-1}+r_{n-2}</cmath>
 +
(From casework on whether the <math>n</math>th position has <math>T</math> or <math>H</math>.).
 +
 
 +
Because <math>r_0=1, r_1=2</math>, we can continue to write out each <math>r_i</math> and hence find <math>c_8=47</math>. Our answer is then <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
 +
 
 +
==Solution 4 (Recursion)==
 +
 
 +
We know that the denominator of the probability is <math>2^8=256</math>. So now we only have to calculate the numerator, which is the number of arrangements for <math>8</math> people at a round table without <math>2</math> or more neighboring people standing.
 +
 
 +
Denote <math>a_n</math> as number of arrangements for <math>n</math> people at a round table without <math>2</math> or more neighboring people standing. We can see that <math>a_2=3</math>, <math>a_3=4</math>, we are going to prove <math>a_n=a_{n-1}+a_{n-2}</math>
 +
 
 +
We use <math>1</math> to represent standing people, and <math>0</math> as sitting people. The problem becomes arranging <math>n</math> numbers of <math>0</math> or <math>1</math> around a circle with no consecutive <math>1</math>'s.
 +
 
 +
We elect one person as the chairman, let him be <math>p_1</math>, the first element in this circular sequence.
 +
There are <math>2</math> cases to generate the arrangement of <math>n</math> numbers.
 +
 
 +
<math>Case</math> <math>1:</math> From the arrangement of <math>n-1</math> numbers, add <math>1</math> more number <math>p_n</math> counter-clockwise next to <math>p_1</math>.
 +
 
 +
If <math>p_1=1</math>, <math>p_{n-1}p_np_1</math> is <math>001</math>, as the diagram shows:
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair A, B, C;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
label("$p_1=1$", A, N);
 +
label("$p_n=0$", B, NW);
 +
label("$p_{n-1}=0$", C, SW);
 +
</asy>
 +
 
 +
If <math>p_1=0</math>, <math>p_{n-1}p_np_1</math> is <math>X00</math>, <math>X</math> could be <math>0</math> or <math>1</math>, as the diagram shows:
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair A, B, C;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
label("$p_1=0$", A, N);
 +
label("$p_n=0$", B, NW);
 +
label("$p_{n-1}=X$", C, SW);
 +
</asy>
 +
 
 +
<math>Case</math> <math>2:</math> From the arrangement of <math>n-2</math> numbers, add <math>2</math> more numbers <math>p_{n-1}</math> and <math>p_n</math> counter-clockwise next to <math>p_1</math>.
 +
 
 +
If <math>p_1=1</math>, then <math>p_{n-2}=0</math>, let <math>p_{n-1}=1, p_n=0</math>, <math>p_{n-1}p_np_1</math> is <math>101</math>, as the diagram shows:
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair A, B, C;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
label("$p_1=1$", A, N);
 +
label("$p_n=0$", B, NW);
 +
label("$p_{n-1}=1$", C, SW);
 +
</asy>
 +
 
 +
If <math>p_1=0</math>, then <math>p_{n-2}</math> could be <math>0</math> or <math>1</math>. Let <math>p_{n-1}=0, p_n=1</math>, <math>p_{n-1}p_np_1</math> is <math>010</math>, as the diagram shows:
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair A, B, C;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
label("$p_1=0$", A, N);
 +
label("$p_n=1$", B, NW);
 +
label("$p_{n-1}=0$", C, SW);
 +
</asy>
 +
 
 +
From the above <math>2</math> cases and the <math>4</math> diagrams, the arrangements of <math>p_{n-1}p_np_1</math> are mutually exclusive collectively exhaustive, so <math>a_{n}=a_{n-1}+a_{n-2}</math>
 +
<math>a_2=3</math>
 +
<math>a_3=4</math>
 +
<math>a_4=7</math>
 +
<math>a_5=11</math>
 +
<math>a_6=18</math>
 +
<math>a_7=29</math>
 +
<math>a_8=47</math>
 +
 
 +
The answer is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>
 +
 
 +
This sequence of numbers is called [https://en.wikipedia.org/wiki/Lucas_number Lucas Number].
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 
 +
==Solution 5 (Recursion)==
 +
Note that there are <math>2^8=256</math> cases in total, so it suffices to find the number of satisfying cases. Define <math>h_n</math> and <math>t_n</math> as sequences of <math>h</math>’s and <math>t</math>’s where no <math>2</math> <math>h</math>’s are adjacent. The sequences will end in <math>h</math> and <math>t</math>, respectively (ignore the fact that they are in a circle for now).
 +
 
 +
In order for a sequence to end in <math>h</math>, the previous term has to be a <math>t</math>; a sequence with a length of <math>n</math> ending in <math>h</math> is equivalent to adding <math>h</math> to the end of a sequence of length <math>n-1</math> that ends with <math>t</math>. This means <math>h_n=t_{n-1}</math>.
 +
 
 +
In order for a sequence to end in <math>t</math>, the previous term can be <math>h</math> or <math>t</math>, so <math>t_n=t_{n-1}+h_{n-1}</math>.
 +
 
 +
Now, we have to take account of the circle. Notice that <math>t_n</math> does not depend on if the people are in a circle or not, but <math>h_n</math> does. To guarantee that some sequence that ends with <math>h</math> does not start with <math>h</math>, we have to add a <math>t</math> in the beginning of the sequence. Since there are <math>n-1</math> terms left, there are <math>h_{n-1}</math> sequences which end with <math>h</math> that satisfy the circle condition.
  
===Solution 5===
+
The length of our sequence is <math>8</math>, so we need to find <math>t_8+h_7</math>. Manipulating our recursions, we can find that <math>t_n=t_{n-1}+t_{n-1}</math>. Now, we proceed to find our terms.
We will count the number of valid arrangements and then divide by <math>2^8</math> at the end. We proceed with casework on how many people are standing.
 
  
Case <math>1:</math> <math>0</math> people are standing. This yields <math>1</math> arrangement.
+
<math>t_1=1</math>
 +
 
 +
<math>t_2=2</math>
 +
 
 +
<math>t_3=3</math>
 +
 
 +
<math>t_4=5</math>
 +
 
 +
<math>t_5=8</math>
 +
 
 +
<math>t_6=13</math>
 +
 
 +
<math>t_7=21</math>
  
Case <math>2:</math> <math>1</math> person is standing. This yields <math>8</math> arrangements.
+
<math>t_8=34</math>
  
Case <math>3:</math> <math>2</math> people are standing. To do this, we imagine having 6 people with tails in a line first. Notate "tails" with <math>T</math>. Thus, we have <math>TTTTTT</math>. Now, we look to distribute the 2 <math>H</math>'s into the 7 gaps made by the <math>T</math>'s. We can do this in <math>{7 \choose 2}</math> ways. However, note one way does not work, because we have two H's at the end, and the problem states we have a table, not a line. So, we have <math>{7 \choose 2}-1=20</math> arrangements.
+
Since <math>h_7=t_6</math> due to the fact that <math>h_n=t_{n-1}</math>, our answer is <math>\frac{34+13}{256}=\boxed{\textbf{(A) } \dfrac{47}{256}}</math>.
  
Case <math>4:</math> <math>3</math> people are standing. Similarly, we imagine 5 <math>T</math>'s. Thus, we have <math>TTTTT</math>. We distribute 3 <math>H</math>'s into the gaps, which can be done <math>{6 \choose 3}</math> ways. However, 4 arrangements will not work. (See this by putting the H's at the ends, and then choosing one of the remaining 4 gaps: <math>{4 \choose 1}=4</math>) Thus, we have <math>{6 \choose 3}-4=16</math> arrangements.
+
~kn07
  
Case <math>5:</math> <math>4</math> people are standing. This can clearly be done in 2 ways: <math>HTHTHTHT</math> or <math>THTHTHTH</math>. This yields <math>2</math> arrangements.
+
== Video Solution by Richard Rusczyk ==
  
Summing the cases, we get <math>1+8+20+16+2=47</math> arrangements.
+
https://www.youtube.com/watch?v=krlnSWWp0I0
Thus, the probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>
 
  
 
== See Also ==
 
== See Also ==

Revision as of 16:13, 21 August 2024

The following problem is from both the 2015 AMC 12A #17 and 2015 AMC 10A #22, so both problems redirect to this page.

Problem

Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

$\textbf{(A)}\dfrac{47}{256}\qquad\textbf{(B)}\dfrac{3}{16}\qquad\textbf{(C) }\dfrac{49}{256}\qquad\textbf{(D) }\dfrac{25}{128}\qquad\textbf{(E) }\dfrac{51}{256}$


Solution 1

We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by $2^8 = 256$ at the end. We casework on how many people are standing.

Case $1:$ $0$ people are standing. This yields $1$ arrangement.

Case $2:$ $1$ person is standing. This yields $8$ arrangements.

Case $3:$ $2$ people are standing. This yields $\dbinom{8}{2} - 8 = 20$ arrangements, because the two people cannot be next to each other.

Case $5:$ $4$ people are standing. Then the people must be arranged in stand-sit-stand-sit-stand-sit-stand-sit fashion, yielding $2$ possible arrangements.

More difficult is:

Case $4:$ $3$ people are standing. First, choose the location of the first person standing ($8$ choices). Next, choose $2$ of the remaining people in the remaining $5$ legal seats to stand, amounting to $6$ arrangements considering that these two people cannot stand next to each other. However, we have to divide by $3,$ because there are $3$ ways to choose the first person given any three. This yields $\dfrac{8 \cdot 6}{3} = 16$ arrangements for Case $5.$

Alternate Case $4:$ Use complementary counting. Total number of ways to choose 3 people from 8 which is $\dbinom{8}{3}$. Sub-case $1:$ three people are next to each other which is $\dbinom{8}{1}$. Sub-case $2:$ two people are next to each other and the third person is not $\dbinom{8}{1}$ $\dbinom{4}{1}$. This yields $\dbinom{8}{3} - \dbinom{8}{1} - \dbinom{8}{1} \dbinom{4}{1} = 16$

Summing gives $1 + 8 + 20 + 2 + 16 = 47,$ and so our probability is $\boxed{\textbf{(A) } \dfrac{47}{256}}$.

Alternate: (Quicksolve) - We know that for case 5, there are 8 ways to choose the first person, and 3 ways to choose the first person given any 3 - which means that for the case, there is 8 * something divided by 3. The sum of the other cases is 31/256. Thus, add a multiple of 8 to 31 to get an answer. The options are 31 + 8 = 39, 31 + 16 = 47, 31 + 24 = 55, etc. The only possible answer is 47/256.

Solution 2

We will count how many valid standing arrangements there are counting rotations as distinct and divide by $256$ at the end. Line up all $8$ people linearly. In order for no two people standing to be adjacent, we will place a sitting person to the right of each standing person. In effect, each standing person requires $2$ spaces and the standing people are separated by sitting people. We just need to determine the number of combinations of pairs and singles and the problem becomes very similar to pirates and gold aka stars and bars aka sticks and stones aka balls and urns.

If there are $4$ standing, there are ${4 \choose 4}=1$ ways to place them. For $3,$ there are ${3+2 \choose 3}=10$ ways. etc. Summing, we get ${4 \choose 4}+{5 \choose 3}+{6 \choose 2}+{7 \choose 1}+{8 \choose 0}=1+10+15+7+1=34$ ways.

Now we consider that the far right person can be standing as well, so we have ${3 \choose 3}+{4 \choose 2}+{5 \choose 1}+{6 \choose 0}=1+6+5+1=13$ ways

Together we have $34+13=47$, and so our probability is $\boxed{\textbf{(A) } \dfrac{47}{256}}$.

Solution 3 (Recursion)

Because the denominator is always $256$, we can count the numerator with a recursion. Define $c_n$ and $r_n$ as the number of satisfying arrangements on a circle and row with $n$ seats, respectively.

Then, observe that \[c_n=r_{n-1}+r_{n-3}\] \[r_n=r_{n-1}+r_{n-2}\] (From casework on whether the $n$th position has $T$ or $H$.).

Because $r_0=1, r_1=2$, we can continue to write out each $r_i$ and hence find $c_8=47$. Our answer is then $\boxed{\textbf{(A) } \dfrac{47}{256}}$.

Solution 4 (Recursion)

We know that the denominator of the probability is $2^8=256$. So now we only have to calculate the numerator, which is the number of arrangements for $8$ people at a round table without $2$ or more neighboring people standing.

Denote $a_n$ as number of arrangements for $n$ people at a round table without $2$ or more neighboring people standing. We can see that $a_2=3$, $a_3=4$, we are going to prove $a_n=a_{n-1}+a_{n-2}$

We use $1$ to represent standing people, and $0$ as sitting people. The problem becomes arranging $n$ numbers of $0$ or $1$ around a circle with no consecutive $1$'s.

We elect one person as the chairman, let him be $p_1$, the first element in this circular sequence. There are $2$ cases to generate the arrangement of $n$ numbers.

$Case$ $1:$ From the arrangement of $n-1$ numbers, add $1$ more number $p_n$ counter-clockwise next to $p_1$.

If $p_1=1$, $p_{n-1}p_np_1$ is $001$, as the diagram shows:

[asy] draw(circle((0, 0), 5)); pair A, B, C; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; label("$p_1=1$", A, N); label("$p_n=0$", B, NW); label("$p_{n-1}=0$", C, SW); [/asy]

If $p_1=0$, $p_{n-1}p_np_1$ is $X00$, $X$ could be $0$ or $1$, as the diagram shows:

[asy] draw(circle((0, 0), 5)); pair A, B, C; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; label("$p_1=0$", A, N); label("$p_n=0$", B, NW); label("$p_{n-1}=X$", C, SW); [/asy]

$Case$ $2:$ From the arrangement of $n-2$ numbers, add $2$ more numbers $p_{n-1}$ and $p_n$ counter-clockwise next to $p_1$.

If $p_1=1$, then $p_{n-2}=0$, let $p_{n-1}=1, p_n=0$, $p_{n-1}p_np_1$ is $101$, as the diagram shows:

[asy] draw(circle((0, 0), 5)); pair A, B, C; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; label("$p_1=1$", A, N); label("$p_n=0$", B, NW); label("$p_{n-1}=1$", C, SW); [/asy]

If $p_1=0$, then $p_{n-2}$ could be $0$ or $1$. Let $p_{n-1}=0, p_n=1$, $p_{n-1}p_np_1$ is $010$, as the diagram shows:

[asy] draw(circle((0, 0), 5)); pair A, B, C; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; label("$p_1=0$", A, N); label("$p_n=1$", B, NW); label("$p_{n-1}=0$", C, SW); [/asy]

From the above $2$ cases and the $4$ diagrams, the arrangements of $p_{n-1}p_np_1$ are mutually exclusive collectively exhaustive, so $a_{n}=a_{n-1}+a_{n-2}$

$a_2=3$
$a_3=4$
$a_4=7$
$a_5=11$
$a_6=18$
$a_7=29$
$a_8=47$

The answer is $\boxed{\textbf{(A) } \dfrac{47}{256}}$

This sequence of numbers is called Lucas Number.

~isabelchen

Solution 5 (Recursion)

Note that there are $2^8=256$ cases in total, so it suffices to find the number of satisfying cases. Define $h_n$ and $t_n$ as sequences of $h$’s and $t$’s where no $2$ $h$’s are adjacent. The sequences will end in $h$ and $t$, respectively (ignore the fact that they are in a circle for now).

In order for a sequence to end in $h$, the previous term has to be a $t$; a sequence with a length of $n$ ending in $h$ is equivalent to adding $h$ to the end of a sequence of length $n-1$ that ends with $t$. This means $h_n=t_{n-1}$.

In order for a sequence to end in $t$, the previous term can be $h$ or $t$, so $t_n=t_{n-1}+h_{n-1}$.

Now, we have to take account of the circle. Notice that $t_n$ does not depend on if the people are in a circle or not, but $h_n$ does. To guarantee that some sequence that ends with $h$ does not start with $h$, we have to add a $t$ in the beginning of the sequence. Since there are $n-1$ terms left, there are $h_{n-1}$ sequences which end with $h$ that satisfy the circle condition.

The length of our sequence is $8$, so we need to find $t_8+h_7$. Manipulating our recursions, we can find that $t_n=t_{n-1}+t_{n-1}$. Now, we proceed to find our terms.

$t_1=1$

$t_2=2$

$t_3=3$

$t_4=5$

$t_5=8$

$t_6=13$

$t_7=21$

$t_8=34$

Since $h_7=t_6$ due to the fact that $h_n=t_{n-1}$, our answer is $\frac{34+13}{256}=\boxed{\textbf{(A) } \dfrac{47}{256}}$.

~kn07

Video Solution by Richard Rusczyk

https://www.youtube.com/watch?v=krlnSWWp0I0

See Also

2015 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 21
Followed by
Problem 23
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
2015 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 16
Followed by
Problem 18
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