P[|X-Y|<=2]<= 3 P[|X-Y|<=1]
I have managed to show P[|X-Y|<=2]<= 5 P[|X-Y|<=1], but the factor of 3 seems to have eluded me. This is problem number 2 in chapter 2 of the text "The Probabilistic Method" by N. Alon and J. H. Spencer, Wiley, 2000.
What is N(p) as a function of p?
Here is a naive computer scientists argument that the answer to this question depends on the continuum hypothesis. Let a0 be aleph 0 and a1 be aleph 1. Treating a0 and a1 as algebraic quantities, suppose that a0 samples are drawn, then the probability that at least one is rational is
1-(1-a0/a1)^(a0) - > 1-((1-a0/a1)^(a1/a0))^(a0^2/a1).
Now suppose that a1 samples are drawn, then the probability that at least one is rational is
1-(1-a0/a1)^(a1) - > 1-((1-a0/a1)^(a1/a0))^(a0).
Since a0/a1 - > 0 lets postulate that (1-a0/a1)^(a1/a0) - > 1/e. Since a0^2/a1=0, the top expression is 0 and the bottom expression is 1. Thus, if N < = aleph 0 then p=0; if N > = aleph 1 then p=1. The only way to obtain 0 < p < 1 is if there is some cardinality between aleph 0 and aleph 1, i.e. the continuum hypothesis.
So can someone put some beef into my argument or are my heuristics just plain false?
Question: For a large enough lattice (m,n), no matter how you color the vertices, there is a set of four monochromatic vertices at the corners of a square (the square may be of any size)?
The original motivation for this problem is to construct a misere game for two players who alternately color the vertices on a large enough grid. The loser is the first player to create such a monochromatic quadruplet.
If you have puzzles that can be solved with some ingenious and creative trick, I would like to know of it!