Greetings
From a group of any 4 students in a class of 30, each has exchanged Christmas cards with the other three. Show that some students have exchanged cards with all the other students in the class. How many such students are there?
Problem
There are 30 students in a class and it is found that in any subset of 4 students from the class each student has exchanged Christmas cards with the other three. Show that some students have exchanged cards with all the other students in the class. How many such students are there?
Student Solutions
How about the combination
1, 2, 3, 4? Of course they have exchanges cards with one another. 1, 5, 6, 7? Yes of course, they have.
1, 8, 9, 10? Sure they did!
1, 11, 12, 13? Yes!
1, 14, 15, 16? Yes!
1, 17, 18, 19? Yes too!
1, 20, 21, 22?
1, 23, 24, 25?
1, 26, 27, 28?
1, 29, 30, 2?
Now comes the conclusion: student number 1 has exchanged cards with everyone else in the class.
How about student number 2? Using the same method, you can find out that he or she has exchanged cards with everyone else as well.
And so did number 3, 4, and everyone else in the class.
The truth is, everyone (30 students) had exchanged cards with everyone else.
Further question: What if, in each subset of 4 students, at least one (but not necessarily all four) had exchanged cards with the other three?