Library / /310 of 740

, 2023

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:

Dorothea has a $3 \times 4$ grid of dots. She colors each dot red, blue, or dark gray. Compute the number of ways Dorothea can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color.

Submit a positive integer $A$ . If the correct answer is $C$ and your answer is $A$ , you will receive $\left\lfloor 20\left(\min \left(\frac{A}{C}, \frac{C}{A}\right)\right)^{2}\right\rfloor$ points.

Solution

Solution:

To find an appropriate estimate, we will lower bound the number of rectangles. Let $P(R)$ be the probability a random $3$ by $4$ grid will have a rectangle with all the same color in the grid. Let $P(r)$ be the probability that a specific rectangle in the grid will have the same color. Note $P(r)=\frac{3}{3^{4}}=\frac{1}{27}$ . Observe that there are $\binom{4}{2}\binom{3}{2}=18$ rectangles in the grid. Hence, we know that $P(R) \leq 18 \cdot P(r)=\frac{18}{27}=\frac{2}{3}$ . Thus, $1-P(R)$ , the probability no such rectangle is in the grid, is at most $\frac{1}{3}$ . This implies that our answer should be at least $\frac{3^{12}}{3}=3^{11}$ , which is enough for around half points. Closer estimations can be obtained by using more values of Inclusion-Exclusion.

n}=
cnt = 0
for i in range( }3**(3*n))
mask = i
a= [[], [], []]
for x in range(3):
for y in range(n):
a[x].append(mask % 3)
mask //= 3
pairs = [set() for i in range(3)]
works = True
for i in range(n):
for j,k in [(0,1), (0,2), (1,2)]:
if a[j]* == a[k]*:
if (j,k) in pairs[a[j]*]:
works = False
else:
pairs[a[j]*].add((j , k))
if works:
cnt += 1
print(cnt)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.