USAMO 2008 — Days 1 and 2 Question 6

At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e. is of the form $2^k$ for some positive integer $k$).

Proposed by Sam Vandervelde; source discussion: https://aops.com/community/p1116182