Difference between revisions of "2024 AMC 8 Problems/Problem 25"

(Standardized Video Solution (3-case reverse casework- super simple!))
m (Punctuation of solution 6 & 7)
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
==Problem 25==
+
== Problem 25 ==
 +
 
 
A small airplane has <math>4</math> rows of seats with <math>3</math> seats in each row. Eight passengers have boarded the plane and are distributed randomly among the seats. A married couple is next to board. What is the probability there will be 2 adjacent seats in the same row for the couple?
 
A small airplane has <math>4</math> rows of seats with <math>3</math> seats in each row. Eight passengers have boarded the plane and are distributed randomly among the seats. A married couple is next to board. What is the probability there will be 2 adjacent seats in the same row for the couple?
  
<math>\textbf{(A)} \frac{8}{15}\qquad\textbf{(B)} \frac{32}{55}\qquad\textbf{(C) } \frac{20}{33}\qquad\textbf{(D) } \frac{34}{55}\qquad\textbf{(E) } \frac{8}{11}</math>
+
<asy>
 +
// Asymptote by aoum
 +
import roundedpath;
 +
unitsize(1cm);
  
==Standardized Video Solution (3-case reverse casework- super simple!)==
+
path p = roundedpath((0,0)--(1,0)--(1,1)--(0,1)--cycle, 0.1);
https://www.youtube.com/watch?v=aNXZGD8gkP0
 
~TheMathGeek
 
  
^^^^^watch
+
for (int r = 0; r < 4; ++r) {
 +
  for (int c = 0; c < 3; ++c) {
 +
    draw(shift(1.1 * c, 1.3 * r) * p);
 +
  }
 +
}
 +
</asy>
  
==Solution 1 (Complementary Counting Casework)==
+
<math>\textbf{(A)} \frac{8}{15}\qquad\textbf{(B)} \frac{32}{55}\qquad\textbf{(C) } \frac{20}{33}\qquad\textbf{(D) } \frac{34}{55}\qquad\textbf{(E) } \frac{8}{11}</math>
 +
 
 +
== Solution 1 (Complementary Counting Casework) ==
  
 
Suppose the passengers are indistinguishable. There are <math>\binom{12}{8} = 495</math> total ways to distribute the passengers. We proceed with complementary counting, and instead, will count the number of passenger arrangements such that the couple cannot sit anywhere. Consider the partitions of <math>8</math> among the rows of <math>3</math> seats, to make our lives easier, assuming they are non-increasing. We have <math>(3, 3, 2, 0), (3, 3, 1, 1), (3, 2, 2, 1), (2, 2, 2, 2)</math>.  
 
Suppose the passengers are indistinguishable. There are <math>\binom{12}{8} = 495</math> total ways to distribute the passengers. We proceed with complementary counting, and instead, will count the number of passenger arrangements such that the couple cannot sit anywhere. Consider the partitions of <math>8</math> among the rows of <math>3</math> seats, to make our lives easier, assuming they are non-increasing. We have <math>(3, 3, 2, 0), (3, 3, 1, 1), (3, 2, 2, 1), (2, 2, 2, 2)</math>.  
Line 24: Line 33:
  
  
For the fourth partition, there is <math>1</math> way to permute the partition. As said before, rows with <math>2</math> passengers can be arranged in <math>3</math> ways, so we obtain <math>3^4 = 81</math> cases.
+
For the fourth partition, there is <math>1</math> way to permute the partition. As said before, rows with <math>2</math> passengers can be arranged in <math>3</math> ways, so we obtain <math>3^4 = 81</math> cases.
  
  
 
Collectively, we obtain a total of <math>6 + 108 + 81 = 195</math> cases. The final probability is <math>1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}</math>.
 
Collectively, we obtain a total of <math>6 + 108 + 81 = 195</math> cases. The final probability is <math>1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}</math>.
  
~blueprimes [https://artofproblemsolving.com/community/user/1096417]
+
~[{{SERVER}}/community/user/1096417 blueprimes], [[User:Wrenmath|Wrenmath]]
 
 
~Edits by [[User: Wrenmath|Wrenmath]]
 
  
==Solution 2 (Straightforward Casework)==
+
== Solution 2 (Straightforward Casework) ==
  
 
Suppose the passengers are indistinguishable.  
 
Suppose the passengers are indistinguishable.  
Line 59: Line 66:
 
~rhydon516  
 
~rhydon516  
  
==Solution 3 (Complementary Casework on Middle Seats) ==  
+
== Solution 3 (Complementary Casework on Middle Seats) ==  
  
 
We notice that if we have a middle seat in a row, then the couple cannot sit in that row. So, we perform complementary casework.  
 
We notice that if we have a middle seat in a row, then the couple cannot sit in that row. So, we perform complementary casework.  
Line 93: Line 100:
 
~NTfish
 
~NTfish
  
==Solution 4 (Permutations, Fastest + Simplest Written Solution)==
+
== Solution 4 (Permutations, Fastest + Simplest Written Solution) ==
 +
 
 
There are <math>12\cdot 11 = 132</math> for two people (the married couple) to be seated. This will be our denominator.
 
There are <math>12\cdot 11 = 132</math> for two people (the married couple) to be seated. This will be our denominator.
  
Line 110: Line 118:
 
Remark: This solution is flawed because if there are <math>9+2=11</math> people on the plane, the probablity could not be calculated this way, because intuitively, the probability should be decreased (as the probability for 9 people and 1 couple is <math>\frac{19}{55}</math>), not increased (to be <math>\frac{2}{3}</math>). -ericz
 
Remark: This solution is flawed because if there are <math>9+2=11</math> people on the plane, the probablity could not be calculated this way, because intuitively, the probability should be decreased (as the probability for 9 people and 1 couple is <math>\frac{19}{55}</math>), not increased (to be <math>\frac{2}{3}</math>). -ericz
  
==Solution 5 ==
+
== Solution 5 ==
  
 
Consider the couple seated together and there should be 8 seated ways (2 ways in each row). And the other 8 people can be seated in other 10 seats randomly.  
 
Consider the couple seated together and there should be 8 seated ways (2 ways in each row). And the other 8 people can be seated in other 10 seats randomly.  
Line 139: Line 147:
 
- Orlando Liu Cupertino Middle School
 
- Orlando Liu Cupertino Middle School
  
 +
== Solution 6 (A Directed Graph) ==
 +
 +
Notice there are <math>\binom{12}{4} = 495</math> ways to distribute <math>4</math> empty seats and <math>8</math> occupied seats without constraints, and that this may be represented as the number of paths from <math>A</math> to <math>B</math> in the directed graph below. This graph is not a diagram of the plane; rather, a node at coordinates <math>(x,y)</math> refers to the number of <math>(occupied,empty)</math> seats that have been placed since leaving <math>A</math>.
 +
 +
Beginning from <math>A</math> we move up one node when adding an empty seat or right one node when adding an occupied seat as we fill the airplane by row. After three such moves, for example, we arrive at the leftmost dashed line, indicating row one is complete. The number adjacent to a node indicates the number of unique paths to a node and is simply the sum of its incoming paths. We arrive at <math>B(8~full, 4~empty)</math> with a total of <math>495</math> unconstrained combinations as expected.
 +
 +
<asy>
 +
size(300);
 +
 +
int xmax = 8;
 +
int ymax = 4;
 +
 +
int [] path_counts = {1,1,1,1,1,1,1,1,1,
 +
                      1,2,3, 4, 5,6,7,8,9,
 +
                      1,3,6,10,15,21,28,36,45,
 +
                      1,4,10,20,35,56,84,120,165,
 +
                      1,5,15,35,70,126,210,330,495};
 +
 +
// Draw filled row lines
 +
draw((3,0)--(0,3), orange+dashed);
 +
draw((7,-1)--(1,5), orange+dashed);
 +
draw((9,0)--(4,5), orange+dashed);
 +
draw((9,3)--(7,5), orange+dashed);
 +
label(scale(.6)*rotate(-45)*"$row~2~filled$", (1,5), NE, orange);
 +
label(scale(.6)*rotate(-45)*"$row~3~filled$", (4,5), NE, orange);
 +
 +
// Draw vertical grid segments: from (x,y) to (x,y+1)
 +
for (int x = 0; x <= xmax; ++x) {
 +
  for (int y = 0; y < ymax; ++y) {
 +
    draw((x,y)--(x,y+1), gray+0.6/*,Arrow(TeXHead,NoFill)*/);
 +
  }
 +
}
 +
 +
// Draw horizontal grid segments: from (x,y) to (x+1,y)
 +
for (int y = 0; y <= ymax; ++y) {
 +
  for (int x = 0; x <= xmax; ++x) {
 +
    if (x < xmax)
 +
      draw((x,y)--(x+1,y), gray+0.6);
 +
    if (path_counts[x+y*9] > 0) {
 +
      string s="$"+string(path_counts[x+y*9])+"$";
 +
      label(scale(.8)*s, (x,y), NE);
 +
    }
 +
 +
  }
 +
}
 +
 +
// Axis labels
 +
label("$full~seats$", (xmax/2,0), S);
 +
label(rotate(90)*"$empty~seats$", (0,ymax/2), W);
 +
 +
label("$A(0,0)$", (0,0), SW);
 +
label("$B(8~full, 4~empty)$", (xmax,ymax+0.5), NE);
 +
 +
</asy>
 +
 +
Next, let's modify our graph to accommodate the complementary case where no adjacent empty seats are allowed. Each empty seat must be followed by a full seat — excepting the final end seat in a row — and is indicated by a path rising and curving right. Once again, the number of paths to a node is the sum of incoming paths, and we thus arrive at <math>195</math> ways to distribute <math>4</math> empty seats with none adjacent.
 +
 +
<asy>
 +
size(300);
 +
 +
int xmax = 8;
 +
int ymax = 4;
 +
int [] draw_these_arcs = {1,1,1,1,1,1,1,0,0,
 +
                    0,1,1,1,1,1,1,1,0,
 +
                    0,1,1,1,1,1,1,1,0,
 +
                    0,0,1,1,1,1,1,1,1,
 +
                    0,0,0,0,0,0,0,0,0};
 +
 +
int [] draw_these_horizontal = {1,1,1,1,1,1,0,0,0,
 +
                    0,1,1,1,1,1,1,0,0,
 +
                    0,1,1,1,1,1,1,0,0,
 +
                    0,0,1,1,1,1,1,1,0,
 +
                    0,0,1,1,1,1,1,1,0};
 +
 +
int [] path_counts = {1,1,1,1,1,1,1,0,0,
 +
                    0,1,3,3,4,6,6,7,0,
 +
                    0,1,1,4,11,11,17,30,0,
 +
                    0,0,1,6,6,17,45,45,75,
 +
                    0,0,1,1,7,30,30,75,195};
 +
 +
import geometry;
 +
 +
// Draw filled row lines
 +
draw((3,0)--(0,3), orange+dashed);
 +
draw((7,-1)--(1,5), orange+dashed);
 +
draw((8,1)--(4,5), orange+dashed);
 +
draw((9,3)--(7,5), orange+dashed);
 +
label(scale(.6)*rotate(-45)*"$row~2~filled$", (1,5), NE, orange);
 +
label(scale(.6)*rotate(-45)*"$row~3~filled$", (4,5), NE, orange);
 +
 +
// Draw grid segments
 +
for (int x = 0; x <= xmax; ++x) {
 +
  for (int y = 0; y <= ymax; ++y) {
 +
    if (draw_these_horizontal[x+y*9] > 0)
 +
      draw((x,y)--(x+1,y), gray+0.6);
 +
    if (path_counts[x+y*9] > 0) {
 +
      string s="$"+string(path_counts[x+y*9])+"$";
 +
      label(scale(.8)*s, (x,y), NE);
 +
    }
 +
    if (draw_these_arcs[x+y*9] > 0) {
 +
      if ((x+y+1)%3 > 0)
 +
        draw(arc((x+1,y),1,90,180),gray+0.6); //Draws the arc
 +
      else
 +
        draw((x,y)--(x,y+1), gray+0.6);
 +
    }
 +
  }
 +
}
 +
 +
// Axis labels
 +
label("$full~seats$", (xmax/2,0), S);
 +
label(rotate(90)*"$empty~seats$", (0,ymax/2), W);
 +
 +
label("$A(0,0)$", (0,0), SW);
 +
label("$B(8~full, 4~empty)$", (xmax,ymax+0.5), NE);
 +
 +
</asy>
 +
 +
Our lucky couple's final probability of sitting together is <math>1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}</math>.
 +
 +
[[User:Skookum_Math|~Skookum_Math]]
 +
 +
== Solution 7 (Polynomials are Wonderful) ==
 +
 +
Let's count the complementary case of distributing empty seats with none adjacent. Beginning with the first row, there is <math>1</math> way to fill the row with no empty seats. There are <math>3</math> ways to complete the row with <math>1</math> empty seat. There is <math>1</math> way to complete the row with <math>2</math> empty seats. There is no way to fit <math>3</math> non-adjacent empty seats.
 +
 +
Let's represent these values as a polynomial where the exponents represent the number of empty seats and the coefficients represent the associated number of possible combinations. For the first row, we have <math>1x^2 + 3x^1 + 1x^0</math>. We have no intention of assigning or determining any value for <math>x</math>. Our polynomial simply keeps our calculations organized.
 +
 +
Let's consider the case of one empty seat in the second row. There are 3 positions it could be in, so we'd represent that as <math>3x^1</math>, of course. If we ask how many combinations exist for a single empty seat in the first row and a single empty seat in the second row, we multiply the <math>3x^1</math> from the first row by the <math>3x^1</math> from the second row and arrive at <math>9x^2</math>, i.e., <math>9</math> combinations of <math>2</math> empty seats with one in each row.
 +
 +
Are there other ways to arrive at <math>2</math> empty seats anywhere in the first two rows? Yes, we could have <math>1x^2</math> in the first row and <math>1x^0</math> in the second row, or vice versa. So the total number of ways to populate <math>2</math> empty seats in the first two rows is <math>1x^2\cdot1x^0 + 3x^1\cdot3x^1 + 1x^0\cdot1x^2 = 11x^2</math>.
 +
 +
Notice that multiplying our original polynomial <math>1x^2 + 3x^1 + 1x^0</math> by the same polynomial for the second row produces the <math>11x^2</math> term above, and similarly produces a count of the combinations for every other possible number of empty seats in the first two rows, i.e., <math>(1x^2 + 3x^1 + 1x^0)^2 = 1x^4 + 6x^3 + 11x^2 + 6x^1 + 1x^0</math>; how wonderful.
 +
 +
<asy>
 +
import roundedpath;
 +
size(150);
 +
import graph;
 +
import fontsize;
 +
 +
int [] digits = {
 +
  -1,-1,1,3,1,
 +
  -1,-1,1,3,1,
 +
  -1,-1,1,3,1,
 +
  -1, 3,9,3,0,
 +
  1, 3,1,0,0,
 +
  1, 6,11,6,1
 +
};
 +
 +
int xmax = 4;
 +
int ymax = 5;
 +
real ys = 0.6;
 +
 +
for (int x = 0; x <= xmax; ++x) {
 +
  for (int y = 0; y <= ymax; ++y) {
 +
 +
    int d = digits[x+(ymax-y)*(xmax+1)];
 +
    if (d > 0) {
 +
      string s="$"+string(d)+"$";
 +
      string s2="$";
 +
      if (d >= 10)
 +
        s2=s2+"\,"; // add space left of x
 +
      if (d >= 100)
 +
        s2=s2+"~"; // more space
 +
      s2=s2+"x^"+string(xmax-x)+"$";
 +
      label(scale(.8)*s, (x,y*ys));
 +
      if (y < 1 || y > 3)
 +
        label(scale(.8)*s2, (x,y*ys), E, gray+0.3);
 +
    }
 +
  }
 +
}
 +
 +
// Draw multiplication symbol
 +
label("$\times$", (-0.8,4*ys), fontsize(12pt));
 +
 +
// Horizontal line below multiplier
 +
draw((-1,3.5*ys)--(4.5,3.5*ys));
 +
 +
// Draw addition symbol
 +
label("$+$", (-0.8,ys), fontsize(12pt));
 +
 +
// Horizontal line below sum
 +
draw((-1,.6*ys)--(4.5,.6*ys));
 +
</asy>
 +
 +
We conclude that <math>(1x^2 + 3x^1 + 1x^0)^4</math> will contain our answer when considering all four rows of our airplane. Or, using our prior product, <math>(1x^4 + 6x^3 + 11x^2 + 6x^1 + 1x^0)^2</math> would be even easier to compute, especially since we only need to make calculations resulting in <math>x^4</math> terms, i.e., <math>x^4\cdot x^0</math> and <math>x^3\cdot x^1</math>, etc. We proceed with <math>2(1x^4\cdot1x^0 + 6x^3\cdot6x^1) + 11x^2\cdot11x^2 = 195x^4</math>. There are <math>195</math> ways to fit four empty seats in our airplane with no two adjacent.
 +
 +
<asy>
 +
import roundedpath;
 +
size(250);
 +
import graph;
 +
import fontsize;
 +
 +
int [] digits = {
 +
  -1,-1,-1,-1,1,6,11,6,1,
 +
  -1,-1,-1,-1,1,6,11,6,1,
 +
  -1,-1,-1,-1,1,6,11,6,1,
 +
  -1, -1,-1,6,36,66,36,6,0,
 +
  -1,-1,11,66,121,66,11,0,0,
 +
  -1,6,36,66,36,6,0,0,0,
 +
  1,6,11,6,1,0,0,0,0,
 +
  1,12,58,144,195,144,58,12,1
 +
};
 +
 +
int xmax = 8;
 +
int ymax = 7;
 +
real ys = 0.7;
 +
 +
for (int x = 0; x <= xmax; ++x) {
 +
  for (int y = 0; y <= ymax; ++y) {
 +
    int d = digits[x+(ymax-y)*(xmax+1)];
 +
    if (d > 0) {
 +
      string s="$"+string(d)+"$";
 +
      string s2="$";
 +
      if (d >= 10)
 +
        s2=s2+"\,"; // add space left of x
 +
      if (d >= 100)
 +
        s2=s2+"~"; // more space
 +
      s2=s2+"x^"+string(xmax-x)+"$";
 +
 +
      label(scale(.8)*s, (x,y*ys));
 +
      if (y < 1 || y > 5)
 +
        label(scale(.8)*s2, (x,y*ys), E, gray+0.3);
 +
    }
 +
  }
 +
}
 +
 +
// Draw multiplication symbol
 +
label("$\times$", (-0.8,6*ys), fontsize(12pt));
 +
 +
// Horizontal line below multiplier
 +
draw((-1,5.5*ys)--(8.5,5.5*ys));
 +
 +
// Draw addition symbol
 +
label("$+$", (-0.8,ys), fontsize(12pt));
 +
 +
// Horizontal line below sum
 +
draw((-1,.6*ys)--(8.5,.6*ys));
 +
 +
// Draw inclined rounded rectangle
 +
// Define the two points (ends of the rectangle)
 +
pair A = (4,0*ys);
 +
pair B = (4,5*ys);
 +
real w = 0.3; // Half the total width (i.e., total width = 1.0)
 +
 +
// Compute the unit direction vector from A to B
 +
pair dir = unit(B - A);
 +
 +
// Compute the perpendicular vector for the width
 +
pair perp = rotate(90)*dir * w;
 +
 +
// Define the 4 corners of the rectangle (CCW or CW)
 +
pair p1 = A + perp - dir*w;
 +
pair p2 = B + perp + dir*w;
 +
pair p3 = B - perp + dir*w;
 +
pair p4 = A - perp - dir*w;
 +
 +
// Build the path
 +
path rect = p1 -- p2 -- p3 -- p4 -- cycle;
 +
 +
// Make it rounded
 +
path rrect = roundedpath(rect, w/1.1);
 +
 +
// Draw it
 +
draw(rrect, orange+0.4+1bp);//+1bp);
 +
</asy>
  
==Video Solution 1 by Math-X (First understand the problem!!!)==
+
Dividing this by the number of unconstrained ways to fit four empty seats in our plane gives the probability that our couple cannot sit together.
https://youtu.be/BaE00H2SHQM?si=mCibdgEbhXc7hd9t&t=8376
 
  
~Math-X
+
To compute the number of unconstrained ways to fit four empty seats anywhere in our airplane, we have a choice of calculating <math>(1x^3 + 3x^2 + 3x^1 +1x^0)^4</math> or <math>(1x^1+1x^0)^{12}</math> or perhaps just <math>\binom{12}{4} = 495</math> this time.
  
==Video Solution by Central Valley Math Circle (Goes through full thought process)==
+
Our married couple's final probability of sitting together is <math>1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}</math>.
https://youtu.be/D2Ft0gFD74k
 
  
~mr_mathman
+
[[User:Skookum_Math|~Skookum_Math]]
  
==Video Solution (A Clever Explanation You’ll Get Instantly)==
 
https://youtu.be/5ZIFnqymdDQ?si=wchnGs6jFqM1__i1&t=3944
 
~hsnacademy
 
  
==Video Solution 2 by OmegaLearn.org==
+
== Video Solution 1 ==
 +
 
 +
[//youtu.be/BaE00H2SHQM?si=mCibdgEbhXc7hd9t&t=8376 ~Math-X]
 +
 
 +
== Video Solution 2 by Central Valley Math Circle (Goes through full thought process) ==
 +
 
 +
[//youtu.be/D2Ft0gFD74k ~mr_mathman]
 +
 
 +
== Video Solution 3 ==
 +
 
 +
[//youtu.be/5ZIFnqymdDQ?si=wchnGs6jFqM1__i1&t=3944 ~hsnacademy]
 +
 
 +
== Video Solution 4 by OmegaLearn.org ==
 
https://youtu.be/WYxfsShInyM
 
https://youtu.be/WYxfsShInyM
  
==Video Solution 3 by SpreadTheMathLove==
+
== Video Solution 5 by SpreadTheMathLove ==
 +
 
 
https://www.youtube.com/watch?v=ArN4qVlBDTM
 
https://www.youtube.com/watch?v=ArN4qVlBDTM
  
== Video Solution by NiuniuMaths (Easy to understand!) ==
+
== Video Solution 6 ==
https://www.youtube.com/watch?v=PBNyuSg0GX4
 
  
~NiuniuMaths
+
[//www.youtube.com/watch?v=PBNyuSg0GX4 ~NiuniuMaths]
  
== Video Solution by CosineMethod [🔥Fast and Easy🔥]==
+
== Video Solution by 7 CosineMethod ==
  
 
https://www.youtube.com/watch?v=bxZHXPMcsGI
 
https://www.youtube.com/watch?v=bxZHXPMcsGI
==Video Solution by Interstigation==
+
 
 +
== Video Solution 8 by Interstigation ==
 +
 
 
https://youtu.be/ktzijuZtDas&t=3297
 
https://youtu.be/ktzijuZtDas&t=3297
  
==Video Solution (Fastest) by MegaMath==
+
== Video Solution 9 by MegaMath ==
 +
 
 
https://www.youtube.com/watch?v=DgQsljPaE5Y
 
https://www.youtube.com/watch?v=DgQsljPaE5Y
  
==Video Solution by Dr. David==
+
== Video Solution 10 by Dr. David ==
 +
 
 
https://youtu.be/L5UlR5QvEnA
 
https://youtu.be/L5UlR5QvEnA
  
==Video Solution by WhyMath==
+
== Video Solution 11 by WhyMath ==
 +
 
 
https://youtu.be/nz0GYQLOFrM
 
https://youtu.be/nz0GYQLOFrM
  
==Video Solution by Daily Dose of Math (Simple, Certified, and Logical)==
+
== Video Solution 12 by Daily Dose of Math ==
  
https://youtu.be/OwJvuq6F7sQ
+
[//youtu.be/OwJvuq6F7sQ ~Thesmartgreekmathdude]
  
~Thesmartgreekmathdude
+
== Video Solution (3-case reverse casework) ==
 +
[//www.youtube.com/watch?v=aNXZGD8gkP0 ~TheMathGeek]
  
==See Also==  
+
== See Also ==  
 
{{AMC8 box|year=2024|num-b=24|after=Last Problem}}
 
{{AMC8 box|year=2024|num-b=24|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Introductory Combinatorics Problems]]

Latest revision as of 01:55, 10 August 2025

Problem 25

A small airplane has $4$ rows of seats with $3$ seats in each row. Eight passengers have boarded the plane and are distributed randomly among the seats. A married couple is next to board. What is the probability there will be 2 adjacent seats in the same row for the couple?

[asy] // Asymptote by aoum import roundedpath; unitsize(1cm);  path p = roundedpath((0,0)--(1,0)--(1,1)--(0,1)--cycle, 0.1);  for (int r = 0; r < 4; ++r) {   for (int c = 0; c < 3; ++c) {     draw(shift(1.1 * c, 1.3 * r) * p);   } } [/asy]

$\textbf{(A)} \frac{8}{15}\qquad\textbf{(B)} \frac{32}{55}\qquad\textbf{(C) } \frac{20}{33}\qquad\textbf{(D) } \frac{34}{55}\qquad\textbf{(E) } \frac{8}{11}$

Solution 1 (Complementary Counting Casework)

Suppose the passengers are indistinguishable. There are $\binom{12}{8} = 495$ total ways to distribute the passengers. We proceed with complementary counting, and instead, will count the number of passenger arrangements such that the couple cannot sit anywhere. Consider the partitions of $8$ among the rows of $3$ seats, to make our lives easier, assuming they are non-increasing. We have $(3, 3, 2, 0), (3, 3, 1, 1), (3, 2, 2, 1), (2, 2, 2, 2)$.


For the first partition, clearly, the couple will always be able to sit in the row with $0$ occupied seats, so we have $0$ cases here.


For the second partition, there are $\frac{4!}{2!2!} = 6$ ways to permute the partition. Now the rows with exactly $1$ passenger must be in the middle, so this case generates $6$ cases.


For the third partition, there are $\frac{4!}{2!} = 12$ ways to permute the partition. For rows with $2$ passengers, there are $\binom{3}{2} = 3$ ways to arrange them in the row so that the couple cannot sit there. The row with $1$ passenger must be in the middle. We obtain $12 \cdot 3^2 = 108$ cases.


For the fourth partition, there is $1$ way to permute the partition. As said before, rows with $2$ passengers can be arranged in $3$ ways, so we obtain $3^4 = 81$ cases.


Collectively, we obtain a total of $6 + 108 + 81 = 195$ cases. The final probability is $1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}$.

~blueprimes, Wrenmath

Solution 2 (Straightforward Casework)

Suppose the passengers are indistinguishable.

What this question is asking, is really, if 4 empty seats are placed, what is the probability that there are 2 adjacent seats open.

We proceed by casework.


Case 1: There is exactly one pair of open seats. Then the other seat in that row must be occupied. The other two empty seats are distributed across the remaining $3$ rows without being adjacent, which is $\binom{9}{2}-6=30$ cases per pair of open seats for $30\cdot8=240$ total cases.


Case 2: There is one row of open seats. $4$ ways to choose the row and $9$ to choose the final empty seat for $4\cdot9=36$ cases.


Case 3: There are $2$ independent pairs of open seats. Choose the $2$ rows, then the placement of each pair within each row for $\binom{4}{2}\cdot2^2=24$ cases.


In total, we get $240+36+24=300$ cases total for a probability of \[\frac{300}{\binom{12}{4}}=\frac{300}{495}=\boxed{\mathbf{(C)}~\frac{20}{33}}\]

~rhydon516

Solution 3 (Complementary Casework on Middle Seats)

We notice that if we have a middle seat in a row, then the couple cannot sit in that row. So, we perform complementary casework.

Case 1: Four people sitting in middle seats.

In this case, there are 4 people left to order, and 8 seats. This gives $\dbinom{8}{4}$ total combinations for this case.

Case 2: Three people sitting in middle seats.

In this case, there are $\dbinom{4}{3}$ ways to permute the rows in which the middle seat is occupied. For the row in which the people do not occupy the middle row, we must have two people sitting at the ends of the rows to guarantee the couple cannot sit there. So, for the rest of the 3 people, there are 6 possible seats. So, there are $\dbinom{4}{3} \cdot \dbinom{6}{3}$ total combinations.

Case 3: Two people sitting in middle seats.

In this case, there are $\dbinom{4}{2}$ ways to permute the rows in which the middle seat is occupied. For the rows in which the people do not occupy the middle row, we must have two people sitting at the ends of the rows to guarantee the couple cannot sit there. So, for the rest of the 2 people, there are 4 possible seats. So, there are $\dbinom{4}{2} \cdot \dbinom{4}{2}$ total combinations.

Case 4: One person sitting in a middle seat

In this case, there are $\dbinom{4}{1}$ ways to permute the rows in which the middle seat is occupied. For the rows in which the people do not occupy the middle row, we must have two people sitting at the ends of the rows to guarantee the couple cannot sit there. So, for the rest of the last person, there are 2 possible seats. So, there are $\dbinom{4}{1} \cdot \dbinom{2}{1}$ total combinations.

Case 5: Zero people sitting in a middle seat

In this case, we must have every person sitting at the ends of the seats. So, there is only 1 combination.

In total, we have

\[\dbinom{8}{4} + \dbinom{4}{3} \cdot \dbinom{6}{3} + \dbinom{4}{2} \cdot \dbinom{4}{2} + \dbinom{4}{1} \cdot \dbinom{2}{1} +1\]

combinations, or 195 combinations. The final step is to find the total amount of combinations without restrictions. This is simply $\dbinom{12}{4} = 495$. So, finally employing complementary counting, we have that the probability that there will be 2 adjacent seats for the couple is

\[1 - \dfrac{195}{495} = \dfrac{20}{33}.\]

~NTfish

Solution 4 (Permutations, Fastest + Simplest Written Solution)

There are $12\cdot 11 = 132$ for two people (the married couple) to be seated. This will be our denominator.

There are $8$ pairs of seats that are next to each other in the diagram ($2$ per row; left-middle and middle-right). This will be our numerator.

Since there are $8+2=10$ total people on the plane, we should multiply our numerator by that to account for all ways the 10 people could be seated (e.x. the husband and the wife could be switched around and it would still work, same applies to the other passengers)

Therefore, our numerator is $8 \cdot 10 = 80$.

This creates the fraction $\frac{80}{132}$, which simplifies to \[\boxed{(\text{\bf{C}}) \: \frac{20}{33}}.\]

- Siddharth Mirchandani (svm2020), John Adams Middle School


Remark: This solution is flawed because if there are $9+2=11$ people on the plane, the probablity could not be calculated this way, because intuitively, the probability should be decreased (as the probability for 9 people and 1 couple is $\frac{19}{55}$), not increased (to be $\frac{2}{3}$). -ericz

Solution 5

Consider the couple seated together and there should be 8 seated ways (2 ways in each row). And the other 8 people can be seated in other 10 seats randomly.

There will be total $8\cdot P(10, 2)$

Consider two double counting cases.


Case I: the other 8 people are seated in (1, 3) (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3)

It was double counted for couple's seats (1, 1) (1, 2) and (2, 1), (2, 2)

There will be $\frac{8\cdot 6}{2}\times P(8, 8)$


Case II: one whole row is empty and the other 8 people are randomly seated in other rows

It was double counted for couple's seats such as (1, 1) (1, 2) and (1, 2) (1, 3)

There will be $4\cdot P(9, 8)$


So the probability is $\frac{8\cdot P(10, 2)-\frac{8\cdot 2}{2}\cdot P(8, 8)-4\cdot P(9, 8)}{P(12, 8)}$

which simplifies to \[\boxed{(\text{\bf{C}}) \: \frac{20}{33}}.\]

- Orlando Liu Cupertino Middle School

Solution 6 (A Directed Graph)

Notice there are $\binom{12}{4} = 495$ ways to distribute $4$ empty seats and $8$ occupied seats without constraints, and that this may be represented as the number of paths from $A$ to $B$ in the directed graph below. This graph is not a diagram of the plane; rather, a node at coordinates $(x,y)$ refers to the number of $(occupied,empty)$ seats that have been placed since leaving $A$.

Beginning from $A$ we move up one node when adding an empty seat or right one node when adding an occupied seat as we fill the airplane by row. After three such moves, for example, we arrive at the leftmost dashed line, indicating row one is complete. The number adjacent to a node indicates the number of unique paths to a node and is simply the sum of its incoming paths. We arrive at $B(8~full, 4~empty)$ with a total of $495$ unconstrained combinations as expected.

[asy] size(300);  int xmax = 8; int ymax = 4;  int [] path_counts = {1,1,1,1,1,1,1,1,1,                       1,2,3, 4, 5,6,7,8,9,                       1,3,6,10,15,21,28,36,45,                       1,4,10,20,35,56,84,120,165,                       1,5,15,35,70,126,210,330,495};  // Draw filled row lines draw((3,0)--(0,3), orange+dashed); draw((7,-1)--(1,5), orange+dashed); draw((9,0)--(4,5), orange+dashed); draw((9,3)--(7,5), orange+dashed); label(scale(.6)*rotate(-45)*"$row~2~filled$", (1,5), NE, orange); label(scale(.6)*rotate(-45)*"$row~3~filled$", (4,5), NE, orange);  // Draw vertical grid segments: from (x,y) to (x,y+1) for (int x = 0; x <= xmax; ++x) {   for (int y = 0; y < ymax; ++y) {     draw((x,y)--(x,y+1), gray+0.6/*,Arrow(TeXHead,NoFill)*/);   } }  // Draw horizontal grid segments: from (x,y) to (x+1,y) for (int y = 0; y <= ymax; ++y) {   for (int x = 0; x <= xmax; ++x) {     if (x < xmax)       draw((x,y)--(x+1,y), gray+0.6);     if (path_counts[x+y*9] > 0) {       string s="$"+string(path_counts[x+y*9])+"$";       label(scale(.8)*s, (x,y), NE);     }    } }  // Axis labels label("$full~seats$", (xmax/2,0), S); label(rotate(90)*"$empty~seats$", (0,ymax/2), W);  label("$A(0,0)$", (0,0), SW); label("$B(8~full, 4~empty)$", (xmax,ymax+0.5), NE);  [/asy]

Next, let's modify our graph to accommodate the complementary case where no adjacent empty seats are allowed. Each empty seat must be followed by a full seat — excepting the final end seat in a row — and is indicated by a path rising and curving right. Once again, the number of paths to a node is the sum of incoming paths, and we thus arrive at $195$ ways to distribute $4$ empty seats with none adjacent.

[asy] size(300);  int xmax = 8; int ymax = 4; int [] draw_these_arcs = {1,1,1,1,1,1,1,0,0,                      0,1,1,1,1,1,1,1,0,                      0,1,1,1,1,1,1,1,0,                      0,0,1,1,1,1,1,1,1,                      0,0,0,0,0,0,0,0,0};  int [] draw_these_horizontal = {1,1,1,1,1,1,0,0,0,                      0,1,1,1,1,1,1,0,0,                      0,1,1,1,1,1,1,0,0,                      0,0,1,1,1,1,1,1,0,                      0,0,1,1,1,1,1,1,0};  int [] path_counts = {1,1,1,1,1,1,1,0,0,                      0,1,3,3,4,6,6,7,0,                      0,1,1,4,11,11,17,30,0,                      0,0,1,6,6,17,45,45,75,                      0,0,1,1,7,30,30,75,195};  import geometry;  // Draw filled row lines draw((3,0)--(0,3), orange+dashed); draw((7,-1)--(1,5), orange+dashed); draw((8,1)--(4,5), orange+dashed); draw((9,3)--(7,5), orange+dashed); label(scale(.6)*rotate(-45)*"$row~2~filled$", (1,5), NE, orange); label(scale(.6)*rotate(-45)*"$row~3~filled$", (4,5), NE, orange);  // Draw grid segments for (int x = 0; x <= xmax; ++x) {   for (int y = 0; y <= ymax; ++y) {     if (draw_these_horizontal[x+y*9] > 0)       draw((x,y)--(x+1,y), gray+0.6);     if (path_counts[x+y*9] > 0) {       string s="$"+string(path_counts[x+y*9])+"$";       label(scale(.8)*s, (x,y), NE);     }     if (draw_these_arcs[x+y*9] > 0) {       if ((x+y+1)%3 > 0)         draw(arc((x+1,y),1,90,180),gray+0.6); //Draws the arc       else         draw((x,y)--(x,y+1), gray+0.6);     }   } }  // Axis labels label("$full~seats$", (xmax/2,0), S); label(rotate(90)*"$empty~seats$", (0,ymax/2), W);  label("$A(0,0)$", (0,0), SW); label("$B(8~full, 4~empty)$", (xmax,ymax+0.5), NE);  [/asy]

Our lucky couple's final probability of sitting together is $1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}$.

~Skookum_Math

Solution 7 (Polynomials are Wonderful)

Let's count the complementary case of distributing empty seats with none adjacent. Beginning with the first row, there is $1$ way to fill the row with no empty seats. There are $3$ ways to complete the row with $1$ empty seat. There is $1$ way to complete the row with $2$ empty seats. There is no way to fit $3$ non-adjacent empty seats.

Let's represent these values as a polynomial where the exponents represent the number of empty seats and the coefficients represent the associated number of possible combinations. For the first row, we have $1x^2 + 3x^1 + 1x^0$. We have no intention of assigning or determining any value for $x$. Our polynomial simply keeps our calculations organized.

Let's consider the case of one empty seat in the second row. There are 3 positions it could be in, so we'd represent that as $3x^1$, of course. If we ask how many combinations exist for a single empty seat in the first row and a single empty seat in the second row, we multiply the $3x^1$ from the first row by the $3x^1$ from the second row and arrive at $9x^2$, i.e., $9$ combinations of $2$ empty seats with one in each row.

Are there other ways to arrive at $2$ empty seats anywhere in the first two rows? Yes, we could have $1x^2$ in the first row and $1x^0$ in the second row, or vice versa. So the total number of ways to populate $2$ empty seats in the first two rows is $1x^2\cdot1x^0 + 3x^1\cdot3x^1 + 1x^0\cdot1x^2 = 11x^2$.

Notice that multiplying our original polynomial $1x^2 + 3x^1 + 1x^0$ by the same polynomial for the second row produces the $11x^2$ term above, and similarly produces a count of the combinations for every other possible number of empty seats in the first two rows, i.e., $(1x^2 + 3x^1 + 1x^0)^2 = 1x^4 + 6x^3 + 11x^2 + 6x^1 + 1x^0$; how wonderful.

[asy] import roundedpath; size(150); import graph; import fontsize;  int [] digits = {   -1,-1,1,3,1,   -1,-1,1,3,1,   -1,-1,1,3,1,   -1, 3,9,3,0,    1, 3,1,0,0,    1, 6,11,6,1 };  int xmax = 4; int ymax = 5; real ys = 0.6;  for (int x = 0; x <= xmax; ++x) {   for (int y = 0; y <= ymax; ++y) {      int d = digits[x+(ymax-y)*(xmax+1)];     if (d > 0) {       string s="$"+string(d)+"$";       string s2="$";       if (d >= 10)         s2=s2+"\,"; // add space left of x       if (d >= 100)         s2=s2+"~"; // more space       s2=s2+"x^"+string(xmax-x)+"$";       label(scale(.8)*s, (x,y*ys));       if (y < 1 || y > 3)          label(scale(.8)*s2, (x,y*ys), E, gray+0.3);     }   } }  // Draw multiplication symbol label("$\times$", (-0.8,4*ys), fontsize(12pt));  // Horizontal line below multiplier draw((-1,3.5*ys)--(4.5,3.5*ys));  // Draw addition symbol label("$+$", (-0.8,ys), fontsize(12pt));  // Horizontal line below sum draw((-1,.6*ys)--(4.5,.6*ys)); [/asy]

We conclude that $(1x^2 + 3x^1 + 1x^0)^4$ will contain our answer when considering all four rows of our airplane. Or, using our prior product, $(1x^4 + 6x^3 + 11x^2 + 6x^1 + 1x^0)^2$ would be even easier to compute, especially since we only need to make calculations resulting in $x^4$ terms, i.e., $x^4\cdot x^0$ and $x^3\cdot x^1$, etc. We proceed with $2(1x^4\cdot1x^0 + 6x^3\cdot6x^1) + 11x^2\cdot11x^2 = 195x^4$. There are $195$ ways to fit four empty seats in our airplane with no two adjacent.

[asy] import roundedpath; size(250); import graph; import fontsize;  int [] digits = {   -1,-1,-1,-1,1,6,11,6,1,   -1,-1,-1,-1,1,6,11,6,1,   -1,-1,-1,-1,1,6,11,6,1,   -1, -1,-1,6,36,66,36,6,0,    -1,-1,11,66,121,66,11,0,0,   -1,6,36,66,36,6,0,0,0,    1,6,11,6,1,0,0,0,0,    1,12,58,144,195,144,58,12,1 };  int xmax = 8; int ymax = 7; real ys = 0.7;  for (int x = 0; x <= xmax; ++x) {   for (int y = 0; y <= ymax; ++y) {     int d = digits[x+(ymax-y)*(xmax+1)];     if (d > 0) {       string s="$"+string(d)+"$";       string s2="$";       if (d >= 10)         s2=s2+"\,"; // add space left of x       if (d >= 100)         s2=s2+"~"; // more space       s2=s2+"x^"+string(xmax-x)+"$";        label(scale(.8)*s, (x,y*ys));       if (y < 1 || y > 5)          label(scale(.8)*s2, (x,y*ys), E, gray+0.3);     }   } }  // Draw multiplication symbol label("$\times$", (-0.8,6*ys), fontsize(12pt));  // Horizontal line below multiplier draw((-1,5.5*ys)--(8.5,5.5*ys));  // Draw addition symbol label("$+$", (-0.8,ys), fontsize(12pt));  // Horizontal line below sum draw((-1,.6*ys)--(8.5,.6*ys));  // Draw inclined rounded rectangle // Define the two points (ends of the rectangle) pair A = (4,0*ys); pair B = (4,5*ys); real w = 0.3; // Half the total width (i.e., total width = 1.0)  // Compute the unit direction vector from A to B pair dir = unit(B - A);  // Compute the perpendicular vector for the width pair perp = rotate(90)*dir * w;  // Define the 4 corners of the rectangle (CCW or CW) pair p1 = A + perp - dir*w; pair p2 = B + perp + dir*w; pair p3 = B - perp + dir*w; pair p4 = A - perp - dir*w;  // Build the path path rect = p1 -- p2 -- p3 -- p4 -- cycle;  // Make it rounded path rrect = roundedpath(rect, w/1.1);  // Draw it draw(rrect, orange+0.4+1bp);//+1bp); [/asy]

Dividing this by the number of unconstrained ways to fit four empty seats in our plane gives the probability that our couple cannot sit together.

To compute the number of unconstrained ways to fit four empty seats anywhere in our airplane, we have a choice of calculating $(1x^3 + 3x^2 + 3x^1 +1x^0)^4$ or $(1x^1+1x^0)^{12}$ or perhaps just $\binom{12}{4} = 495$ this time.

Our married couple's final probability of sitting together is $1 - \frac{195}{495} = \boxed{\textbf{(C)}~\frac{20}{33}}$.

~Skookum_Math


Video Solution 1

~Math-X

Video Solution 2 by Central Valley Math Circle (Goes through full thought process)

~mr_mathman

Video Solution 3

~hsnacademy

Video Solution 4 by OmegaLearn.org

https://youtu.be/WYxfsShInyM

Video Solution 5 by SpreadTheMathLove

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

Video Solution 6

~NiuniuMaths

Video Solution by 7 CosineMethod

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

Video Solution 8 by Interstigation

https://youtu.be/ktzijuZtDas&t=3297

Video Solution 9 by MegaMath

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

Video Solution 10 by Dr. David

https://youtu.be/L5UlR5QvEnA

Video Solution 11 by WhyMath

https://youtu.be/nz0GYQLOFrM

Video Solution 12 by Daily Dose of Math

~Thesmartgreekmathdude

Video Solution (3-case reverse casework)

~TheMathGeek

See Also

2024 AMC 8 (ProblemsAnswer KeyResources)
Preceded by
Problem 24
Followed by
Last Problem
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 AJHSME/AMC 8 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png