Je viens de tomber sur la page suivante qui donne d'autres arguments intéressants :
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=5976Dans la preuve suivante :
Use induction. assume its true for n-1.
Now, there are 2^n possible states of color, and each point can be either "switched" or not, giving 2^n possible sequences of operations. Therefore, if we cannot get them all black, there must be a set S of k points such that switching every point in S causes no change. Now, each point in S is connected to an even number of points in S, so each point in S has an odd number of neighbours in S. So |S| is even. Now, as each point is connected to an even number of points in S, the number of white vertices in S never changes parity mod 2. Now, fix a vertex V in S. If we can get all points except for V black, then V must also be black due to our parity argument. But this is doable by induction. Hence, result.
je ne comprends pas du tout l'affirmation : "if we cannot get them all black, there must be a set S of k points such that switching every point in S causes no change. "
Si quelqu'un peut m'éclairer sur ce point, merci.