In a class with $23$ students, each pair of students have watched a movie together. Let the set of movies watched by a student be his movie collection. If every student has watched every movie at most once, at least how many different movie collections can these students have?
Problem
Source: Turkey TST 2016 P2
Tags: combinatorics, graph theory
10.04.2016 19:43
In $K_{23},$ the degree of each vertex is exactly $22.$ We color the edge satisfying the following condition: If two edge $e_1,e_2$ comes from a common vertex, we color them with different color. And there is a well-known result: Coloring $K_{n}$ satisfying such condition, the number of color we should use is at least $n-1$(if $n$ is even), or $n$(if $n$ is odd). Edit: oops! Thanks Eary for pointing out, my above statement only give us there are at least $23$ different movies.
10.04.2016 20:56
There might be an example for $23$ different collections, but the problem asks for the minimal number of different collections which an example can be gicen. You're wrong, as the answer is not always $n$ for odd integers $n$. For instance, it's not hard to give an example for $4$ different collections when there are $5$ students total.
21.04.2016 17:13
All the students may have the same movie collection and it gives the answer 1. Am I wrong somewhere?
21.04.2016 21:09
Can you explain your construction?
25.04.2016 15:58
For $n$ students from $1$ to $n$ each pair of students $(i,j)$ watch together movie $i-j \mod n$, is it right?
27.04.2016 19:09
mszew wrote: For $n$ students from $1$ to $n$ each pair of students $(i,j)$ watch together movie $i-j \mod n$, is it right? For a pair $x,y$ of students, how do we decide if it is $x-y$ or $y-x$, modulo $n$?
28.04.2016 04:34
Something is missing i guess... If everyone has seen the same movie, the answer is 1, so is it that every pair of student watched a different movie?
28.04.2016 23:47
godfjock wrote: Something is missing i guess... If everyone has seen the same movie, the answer is 1, so is it that every pair of student watched a different movie? As stated, every $\binom{23}{2}$ pairs have watched a movie, and one student has watched $22$ different movies