Vanity of Vanities, all is Vanity

Is there a one line proof of the following not too hard fact? And if so, what is it?

Claim: If X is a random variable in the range [0,M] with expectation u, then
Var(X) < =u(M-u).

Given a set P of n points in the plane (hallelujah!) color them by black and white (or by gold and lavender if your taste is more tacky), so that if a line has more than, say, 50, points on one side of it, then this side contains at least one white point and at least one black point.

Talking points:

1. This problem is not easy but not too hard. It is taken from some paper. I have my own solution, but its not as elementary as the original solution.
2. 50 is just a convenient constant to talk about. I think 4 or 8 is possible, but if you can do it with any constant thats good.
3. This problem has interesting connections to discrepancy and similar stuff.
4. The 3d version is harder (points and planes) - I dont know its status.

A workshop in France,and a vacation in Washington (the state) consumed without remorse the last three weeks. Now, I am back, and the semester is about to begin. And so the summer had flown away, like an arrow with a jet engine.

Our broadcasts of nonsense and even more nonsense would resume soon…

We all know about eps-nets and eps-approximations (we is used here in the more restricted form, namely its the set of people that know what are eps-nets and eps-approximations [if you don't know what are these creatures, do not despair, you might still be a you {you can be become a we if you read these class notes}]).

Anyway, there are even more bizarre forms of samples used in computational geometry, specifically sensitive and relative approximations. Intuitively, these creatures live in the no man land between nets and approximations and they provide in some cases better results than what is provided by using the standard samples.

Anyway, squared, I put up a short survey of these creatures in my notes pages, see here if you are interested.

A nice piece on Tel-Aviv, where I spent 14 years of my life (I moved there when I was 14, before that I was a farm boy [but once a farm boy, always a farm boy]).

Consider the contrast between this and Bernard’s piece, Taking this to be voltage, one can probably come up with an Ohm law to compute hatred.

Bernard Chazelle visits the Palestinian universities. Interesting. Although the comparison of the Likud to the Hamas is very unsubstantiated considering how the two words are spelled completely differently. I think a better comparison is the Likud to Shakshouka and the Hamas to watermelon (watermelons and Shakshoukas might object to these comparisions, naturally).

And then you can read this joke.

So, you solved part I.
But here is now part II (which is harder, BTW). Now, the board is made out of n coins places on vertices of a regular n-gon. The game is played as before, but here the candidate can choose out of n possible rotations after each step, and the journalist can pick any subset of coins to flip.

Give a full characterisation of all the values of n for which the journalist can win.
(Hint: the characterisation is very simple, but the proof of correctness is not.)

[I might have posted this problem in the past. I am posting it for the second part, which I will post soon.]

A journalist, named Zoe, unfortunately (for her) interviews one of the presidential candidates. The candidate refuses to let Zoe to end the interview, and goes on and on about the candidate’s plans how to solve all the problems in the world. In the end, the candidate offers Zoe a game. If she wins the game she can leave.

The game board is made out of 2×2 coins:

At each round, Zoe can decide to flip one or two coins, by specifying which coins she is flipping (for example, flip the left bottom coin and the right top coin), next the candidate goes and rotates the board by either 90,180,270, or 0 degrees. (Of course, rotation by 0 degrees is just keeping the coins in their current configuration.)

The game is over when all the four coins are either all heads or all tails. To make things interesting, Zoe does not see the board, and does not know the starting configuration.

Describe an algorithm that Zoe can deploy, so that she always win. How many rounds are required by your algorithm?