2
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ But could you or anyone please show an application of the probabilistic method to this problem? $\endgroup$ Jan 4, 2013 at 4:21
  • $\begingroup$ @user15849: I added something about viewing the pigeonhole principle as an instance of the probabilistic method. $\endgroup$
    – joriki
    Jan 4, 2013 at 15:12
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .