Kvant Math Problem 73

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m27s
Source on kvant.digital

Problem

On a lottery ticket, one must mark 8 squares out of 64. What is the probability that after the drawing, in which 8 squares out of 64 are also selected (with all such selections assumed equally likely), exactly 4 squares will have been guessed correctly? Exactly 5 squares? … all 8 squares?

Exploration

Fix the player's marked set of $8$ squares. The drawing is another $8$-element subset of the $64$ squares, chosen uniformly from all $\binom{64}{8}$ possibilities.

The event that exactly $k$ squares are guessed correctly means that the intersection of the player's set and the drawn set has size $k$. To count such drawings, choose which $k$ of the player's $8$ marked squares appear in the drawing, and then choose the remaining $8-k$ drawn squares from the $56$ squares that were not marked by the player.

For a small check, consider a toy version with $8$ squares total and $2$ marked by the player, while the drawing also selects $2$ squares. The number of drawings with exactly one correct guess is $\binom21\binom61=12$, while the total number of drawings is $\binom82=28$. The same counting principle works.

The step most likely to hide an error is the counting of drawings with exactly $k$ correct guesses. One must ensure that every admissible drawing is counted once and only once, and that the remaining $8-k$ squares are chosen from the $56$ unmarked squares, not from all $64-k$ squares.

Problem Understanding

A player marks $8$ squares out of $64$. Independently, the lottery drawing selects $8$ squares out of $64$, each $8$-element subset being equally likely. For each $k=4,5,6,7,8$, we must find the probability that exactly $k$ of the player's marked squares coincide with the drawn squares.

This is a Type C problem, since we are asked to determine specific numerical probabilities.

The core difficulty is counting correctly the number of drawings whose intersection with the player's chosen set has prescribed size $k$.

The answer should be

$$P_k=\frac{\binom{8}{k}\binom{56}{8-k}}{\binom{64}{8}}, \qquad k=4,5,6,7,8.$$

The reason is that one first chooses the correctly guessed squares among the player's $8$ marks, then fills the rest of the drawing from the $56$ squares not marked by the player.

Proof Architecture

The first claim is that the total number of possible drawings equals $\binom{64}{8}$, because every drawing is an $8$-element subset of a $64$-element set.

The second claim is that the number of drawings having exactly $k$ correct guesses equals $\binom{8}{k}\binom{56}{8-k}$, because such a drawing consists of $k$ selected squares from the player's marked set and $8-k$ selected squares from its complement.

The third claim is that dividing this count by the total number of drawings yields the required probability, since all drawings are equally likely.

The most delicate lemma is the second one, because a counting mistake there would invalidate the entire result.

Solution

Let $M$ be the set of the $8$ squares marked by the player. Let $D$ be the set of the $8$ squares selected in the drawing.

Every possible drawing corresponds to an $8$-element subset of the $64$ squares. Since all such subsets are equally likely, the total number of possible drawings is

$$\binom{64}{8}.$$

Fix an integer $k$ with $0\le k\le 8$. We count the drawings for which exactly $k$ squares are guessed correctly, that is,

$$|M\cap D|=k.$$

To construct such a drawing, first choose the $k$ squares of $M$ that belong to $D$. This can be done in

$$\binom{8}{k}$$

ways.

After these $k$ squares have been chosen, the drawing must contain exactly $8-k$ additional squares. None of them may belong to $M$, otherwise the intersection would contain more than $k$ elements. Since $M$ contains $8$ squares, there are

$$64-8=56$$

squares outside $M$. The remaining $8-k$ elements of $D$ can therefore be chosen in

$$\binom{56}{8-k}$$

ways.

Hence the number of drawings with exactly $k$ correct guesses is

$$\binom{8}{k}\binom{56}{8-k}.$$

Since every drawing is equally likely, the probability of exactly $k$ correct guesses is

$$P_k=\frac{\binom{8}{k}\binom{56}{8-k}}{\binom{64}{8}}.$$

Substituting $k=4,5,6,7,8$ gives

$$P_4=\frac{\binom84\binom{56}4}{\binom{64}8},$$

$$P_5=\frac{\binom85\binom{56}3}{\binom{64}8},$$

$$P_6=\frac{\binom86\binom{56}2}{\binom{64}8},$$

$$P_7=\frac{\binom87\binom{56}1}{\binom{64}8},$$

$$P_8=\frac{\binom88\binom{56}0}{\binom{64}8} =\frac1{\binom{64}8}.$$

Thus the required probabilities are

$$\boxed{ P_k=\frac{\binom{8}{k}\binom{56}{8-k}}{\binom{64}{8}, \qquad k=4,5,6,7,8. } }$$

Verification of Key Steps

The crucial counting step is the formula

$$\binom{8}{k}\binom{56}{8-k}.$$

Choose any drawing with exactly $k$ correct guesses. Its intersection with $M$ consists of exactly $k$ elements, determining uniquely one of the $\binom{8}{k}$ choices. The remaining $8-k$ elements lie outside $M$, determining uniquely one of the $\binom{56}{8-k}$ choices. Conversely, every pair of such choices produces a drawing with intersection size exactly $k$. This establishes a bijection.

A common mistake is to choose the remaining $8-k$ squares from all squares not already selected among the correct guesses. That would give $\binom{64-k}{8-k}$ and would allow additional elements of $M$ to enter the drawing, producing more than $k$ correct guesses. Restricting the choice to the $56$ squares outside $M$ avoids this error.

For $k=8$, the formula yields

$$\frac{\binom88\binom{56}0}{\binom{64}8} = \frac1{\binom{64}8},$$

which agrees with direct reasoning: only one drawing coincides exactly with the player's ticket.

Alternative Approaches

The result can be viewed as an instance of the hypergeometric distribution. Among the $64$ squares, the $8$ marked by the player are designated as successes and the remaining $56$ as failures. The drawing samples $8$ squares without replacement. The probability of obtaining exactly $k$ successes is the standard hypergeometric probability

$$\frac{\binom{8}{k}\binom{56}{8-k}}{\binom{64}{8}}.$$

The direct combinatorial argument used above is preferable because it derives the formula from first principles and requires no prior knowledge of probability distributions.