Solution to Week 3 Bonus

This post originally appeared on the Brilliant blog on 9/2/2012.

Bonus Challenge: 8 eager students are in line to take their seats in the first row, which has exactly 8 chairs. The student decides that the first person could pick any chair to sit on. For the rest, they have to pick a seat that is immediately next to another seated student. How many ways are there for the students to seat themselves according to this method?

Key Techniques: Recurrence Relation; Bijection, Injection, Surjection.

Solution 1: Let an a_n be the number of ways to seat n n students in n n seats as specified in the question. For a group of n n students there are an−1 a_{n-1} ways to sit the first n−1 n-1 students. With the restriction that each of the n−1 n-1 students must be seated next to another student, they can either occupy the first n−1 n-1 seats, leaving the last seat empty, or the last n−1 n-1 seats, leaving the first seat empty. Thus,an=2an−1=22an−2=…=2n−1a1 a_n = 2 a_{n-1} = 2^2 a_{n-2} = \ldots = 2^{n-1} a_1. Clearly, a1=1 a_1 = 1, which gives, an=2n−1 a_n = 2^{n-1}. So, we have, a8=27=128 a_8 = 2^{7} = 128.

Solution 2: We create a bijection between the number of ways for the students to sit, and the number of sequences of length 7 where each term is either L or R. (Showing Injection) Given a possible way of seating, we will ignore the first person, and then consider whether the rest chose to sit on the Left (L), or the Right (R) of the seated row of students. This leads to a sequence of length 7 with terms L and R. Given two distinct ways of seating, at least one student made a different decision, so the 2 sequences will be different.

(Showing Surjection) Conversely, given a sequence of length 7 with terms R, L, we associate the ith student with the i-1 term, temporarily ignoring the first student. We proceed to seat the students starting from the back as follows: if their associated term is R, they will take the Rightmost vacant seat, if their associated term is L, they will take the Leftmost vacant seat. This eventually leaves 1 vacant seat, where we will place the first student. Given 2 sequences, looking from the back if the first differ in the i-1 term, then the seating arrangement of the ith student would be different.

Hence, we have a Bijection. It remains to count the number of sequences of length 7, where each term is either L or R. By the product rule, this is equal to 27=128 2^7 = 128 .

Answer: 128

Note by Calvin Lin
8 years ago

2 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

×

Problem Loading...

Note Loading...

Set Loading...