The question is below:
At a bakery the baker made 20 kind of cookies, from each kind he made exactly 20 cookies. Once baked, he randomly put them at 20 table pans, at each table pan he put exactly 20 cookies. Prove that someone can choose one cookie from each of the twenty pan tables (20 in total) without choosing two cookies from the same kind.
I set a graph G with V1 = the twenty kinds, V2 = the twenty table pans and connected between two nodes if and only if the table pan includes a cookie from the kind represented by the other node. Thing is, I want to prove, as a part of the answer that it cant be that a random subset S of V2 is at greater size than its neighbors set. I struggle to grasp it intuitively, and what helps me at those situations is defining a function between the two sets which "overkills" that situation (I've only seen verbal explanation for this). Could you help me define something like that and see the contradiction clearly? Thanks!
If you take $n$ trays, they contain $20n$ cookies. Because there are exactly $20$ of each type, by the pigeon hole principle, there are at least $n$ types of cookies represented. This is exactly the Hall hypothesis.