# A problem involving the lattice grid.

Suppose that $22$ points are arbitrarily chosen from a $7\times 7$ lattice grid. We are to prove that there exists at least one rectangle in any $4$ points chosen from the above $22$.

A general doubt, can we prove combinatorial problems by means of probability? I mean, can we use the fact that if there exists a rectangle, then the probability of occurrence of a rectangle in any $4$ selection is $1$.

Any help appreciated.

-
Noting that $22 = 3 \times 7 + 1$ the pigeonhole principle seems indicated ... – Mark Bennet Jan 3 '13 at 18:34
By "A general doubt" do you mean "As a general question"? – Chris Godsil Jan 3 '13 at 18:51
@Chris: Probably; that’s a pretty common foreignism on this site. – Brian M. Scott Jan 3 '13 at 18:58
@Chris: see meta.math.stackexchange.com/questions/3200/… – joriki Jan 3 '13 at 19:09
@joriki: Worth it just for the exchange between Arturo and cardinal! – Brian M. Scott Jan 3 '13 at 19:18

Yes, we can solve (not "prove") combinatorial problems by means of probabilities; this is the probabilistic method. However, while I'm not sure I understand what you mean by "the probability of occurrence of a rectangle in any $4$ selection is $1$" (what is "any $4$ selection"?), it doesn't sound like a correct application of the probabilistic method to me (as far as I understand it).

There are $\binom72=21$ different pairs of $x$ coordinates. Placing $k_i$ points in row $i$ creates $k_i(k_i-1)/2$ different pairs. If the same pair is created in two different rows, we have a rectangle. With $\sum_i k_i=22$, we have

$$\sum_i\frac{k(k-1)}2=\sum_i\frac{k^2}2-\sum_i\frac k2=\frac{\sum_ik_i^2}2-11$$

pairs in total. Since $\sum_ik_i$ is fixed, $\sum_ik_i^2$ is least if the points are distributed over the rows as uniformly as possible, i.e. with six $k_i$ equal to $3$ and one equal to $4$. Then

$$\frac{\sum_ik_i^2}2-11=\frac{6\cdot9+16}2-11=24\;,$$

so at least one pair must occur at least twice, so there must be a rectangle.

This is an application not of the probabilistic method but of the pigeonhole principle. However, you can view the pigeonhole principle as a special case of the probabilistic method: In a typical application of the probabilistic method, one shows that the average of an integer is less than $1$, and it follows that there is at least one instance where it is $0$. In applying the pigeonhole principle, one shows that the average of an integer is greater than $1$, and it follows that there is at least one instance where it is at least $2$.

-
Thank you so much – Torsten Hĕrculĕ Cärlemän Jan 4 '13 at 4:20
But could you or anyone please show an application of the probabilistic method to this problem? – Torsten Hĕrculĕ Cärlemän Jan 4 '13 at 4:21
@user15849: I added something about viewing the pigeonhole principle as an instance of the probabilistic method. – joriki Jan 4 '13 at 15:12

The way to approach this problem is to use the technique of Double Counting. Specifically, we are going to count the number of column pairs of chosen points in 2 ways.

Proof by contradiction. Let the number of column pairs be $N$. Suppose such a rectangle didn't exist. Then, in any 2 rows, they may have 1 column pair in common. Hence, $N \leq {7 \choose 2} = 21$.

Let's count in another way. If there are $C$ points in a column, then there are $C \choose 2$ column pairs that it contributes. Let Column i have $C_i$ points, then the number of pairs is $N = \sum {C_i \choose 2 } = \frac {1}{2} \sum C_i(C_i - 1)$. How do we minimize this function? By a smoothing argument, we see that the minimum occur when each of the $C_i$ are close to each other, in the sense that $|C_i - C_j| \leq 1$. This occurs when $\{C_i\} = \{ 3, 3, 3, 3, 3, 3, 4 \}$, and the function has value $6 \times {3 \choose 2} + 1 \times { 4 \choose 2} = 24$. This gives $N \geq 24$.

Hence, we have a contradiction since $24 \leq N \leq 21$, so we are done.

We could calculate the minimum by using Jensen's inequality, to obtain the minimum of $7 \times {7 \choose 2} \approx 23.57$. For certain cases, having the stricter version would give us a stronger statement that is necessary to arrive at the contradiction.

-