Calvin Goes to Ten Flags

Let $n$ be the number of people in the group. Define a pair as two people going to the same ride, and let $v$ be the total number of pairs. Number the rides as Rides $1$ , $2$ , ..., $10$ , and let the number of people who rode on Ride $r$ be $x_r$ .

First, we calculate the Maximum value of $v$ by using the fact that any $2$ different people rode at most $2$ rides in common. In that group, there are $^nC_2 = \frac{n(n-1)}{2}$ sets of $2$ people. Each set of 2 people rode a maximum of 2 rides in common, so the maximum number of pairs is $2(\frac{n(n-1)}{2}) = n(n-1)$ . Hence, the number of pairs in that group could not go over $n(n-1)$ , so $v \le n(n-1)$ .

Second, Counting $v$ using the number of pairs formed in each ride

In each ride where there are $p$ people who rode, there are $^pC_2 = \frac{p(p-1)}{2}$ pairs formed. The total number of pairs formed, which is $v$ is $\sum_{i=1}^{10} (^{x_i}C_2) = \sum_{i=1}^{10} \big(\frac{(x_i)(x_i-1)}{2}\big) = \frac{1}{2} (\sum_{i=1}^{10} \big((x_i-\frac{1}{2})^2)-\frac{1}{4}\big)$ . The total number of rides ridden is $5n$ , so $\sum_{i=1}^10 (x_i-\frac{1}{2})$ is equal to $5n-5$ . Through the Cauchy-Schwarz inequality and letting all of $y_1$ , $y_2$ , ..., $y_n$ be $1$ , we get that $(5n-5)^2 \le 10(\sum_{i=1}^{10} (x_i-\frac{1}{2})$ $\rightarrow \sum_{i=1}^{10} (x_i-\frac{1}{2}) \ge \frac{(n-1)(5n-5)}{2}$ . Substituting the inequality in 2.2.3 to the equation in 2.2.1, we get $v \ge \frac{1}{2}(\frac{(n-1)(5n-5)}{2}-\frac{5}{2})=\frac{1}{2}(\frac{5n^2-10n}{2})=\frac{5n^2-10n}{4}$ . Hence, $v \ge \frac{5n^2-10n}{4}$ .

We now combine the 2 inequalities from 2.1 and 2.3 respectively: $v \le n(n-1)$ and $v \ge \frac{5n^2-10n}{4}$ , so $n(n-1) \ge \frac{5n^2-10n}{4}$ $\rightarrow$ $4n(n-1) \ge 5n^2-10n$ $\rightarrow 4n^2-4n \ge 5n^2-10n$ $\rightarrow 6n \ge n^2$ $\rightarrow 6 \ge n$ . Since $n$ is obviously nonnegative, $0 \le n \le 6$ .

Let's show that 6 is possible.
Let Person 1 ride Rides 1, 2, 4, 5, 6.
Let Person 2 ride Rides 3, 4, 6, 7, 8.
Let Person 3 ride Rides 5, 6, 8, 9, 10.
Let Person 4 ride Rides 1, 2, 7, 8, 10.
Let Person 5 ride Rides 2, 3, 4, 9, 10.
Let Person 6 ride Rides 1, 3, 5, 7, 9.
Hence, we are done. The most number of people in the group is 6.

Let there be $k$ people who went to 6-flags. Consider the incidence matrix, with rows listing the $k$ people, and columns listing the 10 rides. Place a 1 in the corresponding cell if the person rode the ride. From the conditions, there are exactly 5 1's in each row, so there are a total of $5k$ 1's in this table.

Let's count the number of column pairs of 1's in 2 ways. Firstly, since any 2 people had at most 2 rides in common, the number of column pairs is at most ${k \choose 2} \times 2$ . Secondly, let $c_i$ denote the number of 1's in each column. We know that $\sum c_i = 5k$ . If there are $c_i$ 1's in column $i$ , then the column will contribute ${c_i \choose 2}$ column pairs. This is a quadratic $\sum \frac {c_i ^2 - c_i} {2}$ , which is minimized when all the $c_i$ are equal to $\frac {5k}{10}$ . Hence, we have the inequality

$10 { \frac {5k}{10} \choose 2} \leq \mbox{number of column pairs} \leq {k \choose 2} \times 2$

which resolves to $10 \times \frac { 5k}{10} \times \frac {5k-10}{10} \leq k (k-1) \times 2 \Rightarrow 5k - 10 \leq 4k-4 \Rightarrow k \leq 6$ .

Note that in order for equality to hold, we must have each $c_i = \frac {5k}{10} = 3$ , and also that each pair of rows must contribute 2 column pairs. This can be satisfied by (having each person ride) $\{1, 2, 3, 4, 5\}, \{1, 2, 6, 7, 8\}, \{2, 3, 6, 9, 10\}$ , $\{3, 4, 7, 8, 9\}, \{4, 5, 6, 8, 10\}, \{1, 5, 7, 9, 10 \}$ .

Let be the number of people in the group. Define a pair as two people going to the same ride, and let be the total number of pairs. Number the rides as Rides , , ..., , and let the number of people who rode on Ride be . First, we calculate the Maximum value of by using the fact that any different people rode at most rides in common. In that group, there are sets of people. Each set of 2 people rode a maximum of 2 rides in common, so the maximum number of pairs is . Hence, the number of pairs in that group could not go over , so . Second, Counting using the number of pairs formed in each ride In each ride where there are people who rode, there are pairs formed. The total number of pairs formed, which is is . The total number of rides ridden is , so is equal to . Through the Cauchy-Schwarz inequality and letting all of , , ..., be , we get that . Substituting the inequality in 2.2.3 to the equation in 2.2.1, we get . Hence, . We now combine the 2 inequalities from 2.1 and 2.3 respectively: and , so . Since is obviously nonnegative, . Let's show that 6 is possible. Let Person 1 ride Rides 1, 2, 4, 5, 6. Let Person 2 ride Rides 3, 4, 6, 7, 8. Let Person 3 ride Rides 5, 6, 8, 9, 10. Let Person 4 ride Rides 1, 2, 7, 8, 10. Let Person 5 ride Rides 2, 3, 4, 9, 10. Let Person 6 ride Rides 1, 3, 5, 7, 9. Hence, we are done. The most number of people in the group is 6.

If we start drawing Venn diagrams, we will get 6 circles with maximum of two roller coasters in common. If the roller coasters are A,B,C,D,E,F,G,H,I,J. Then, we will get the following combinations. A,B,C,D,E C,D,E,F,G A,B,F,G,I J,H,C,I,A J,H,B,D,F J,C,G,A,F These are the only six combinations we get. So, the number of friends will be 6.