Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 2 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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