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