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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.