And, in case you solve the previous puzzle too quickly, here is another one.
Is it always possible to partition a class of n students into two subsets such that no student has more than half of his friends in his own subset? Here n is an arbitrary integer.
Lemme give this one a try!
I'll assume that if A is B's friend, then B is A's friend- that is, friendship is symmetric.
For each partition of students, we can calculate the number
N = (# of friendships between students in different subsets) - (# of friendships between students in the same subset).
Ideally, we want a partition with a lot of friendships between different subsets, so we want N to be as big as possible. This is good, since there are a finite number of possible partitions, so there exists a partition for which N is maximized. That is, no other partition has a bigger N (though they can tie for biggest). Call this the 'optimal partition'.
Suppose that in the optimal partition, there exists a student who has more than half his friends in his own subset. Then simply move that one student into the other subset. It's easy to see that when you do this, only friendships which involve this one student are affected. Furthermore, moving this one student must strictly increase N.
However, we assumed that this 'optimal partition' had the maximum value for N, so this is a contradiction. Thus, our optimal partition cannot contain a student with more than half his friends in his own subset, which is exactly what the problem asks for!
---
I think that works. Is there an easier way?
If I'm right, then I have another puzzle for everyone: Every number from 1, 2, 3, ..., all the way to infinity, is painted either red, blue, green, or yellow. Must there exist two numbers, painted the same color, that differ by a perfect square?
Actually I can solve it without using the heating. I turn one switch on and leave it on for a couple of months, until the bulb will surely burn. Then I turn that swithc off, turn on another switch and go into the room ...
If you can't go into the room to check out if the bulb is burnt out how the Hell would you know when to turn on another switch? Tell me how it's done without causing some physical clue that doesn't involve walking in the other room? Obviously the riddle included the heated bulb.
Wait 3 years. The probability that an ordinary bulb will still be OK after such a long time is probably much lower than the probability that Earth will be hit by a giant asteroid.
You are stubborn.