Olympiad Maths Prep

Library / /43 of 55

Combinatorics Difficulty 6.6 National olympiad Prove it Ukraine

A 3×33 \times 3 table has positive integers in its cells so that the sum of numbers in any two cells that share common side is a factorial of a positive integer. Show that there are at least 33 equal numbers in the table.
The factorial of a positive integer nn is a product 123n1 \cdot 2 \cdot 3 \cdots n.

Figure 1
Fig. 5

Solution

We will start with the following lemma.
Lemma 1. There exists a diagonal that has two equal numbers for any 2×22 \times 2 square.
Proof. Let XX be the greatest number in 2×22 \times 2 square. Let his neighbors in this 2×22 \times 2 square be AA and BB. Clearly, they are located on a diagonal, so if A=BA = B, the lemma is proven. Suppose A>BA > B. Then A+X=k!>B+X=m!>1A + X = k! > B + X = m! > 1, thus k>mk > m. It is also clear that m>1,k>2m > 1, k > 2. But then
2(B+X)=2m!>2XA+X=k!km!>2m!, 2(B + X) = 2m! > 2X \ge A + X = k! \ge k \cdot m! > 2m!,
that leads to a contradiction. This finishes the proof of Lemma 1.

By contradiction, suppose a,b,c,d,e,f,g,h,ia, b, c, d, e, f, g, h, i are in the table (Fig. 5). By Lemma 1 for the square that consists of a,b,d,ea, b, d, e either b=db = d or a=ea = e. In the first case, we will use Lemma 1 for the square with d,e,g,hd, e, g, h, and then for b,c,e,fb, c, e, f. Thus, either b=d=hb = d = h, or b=d=fb = d = f, or g=e=cg = e = c.

In the second case, we will use Lemma 1 for e,f,h,ie, f, h, i, and then for b,c,e,fb, c, e, f. Thus, either a=e=ia = e = i or a=e=ca = e = c, or h=f=bh = f = b. In all cases we obtain three equal numbers.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.