Maths Olympiad Prep

Library / /8 of 9

Combinatorics Difficulty 8.0 National olympiad, round 2 Prove it Japan

Consider an operation of putting an integer greater than or equal to 11 and less than or equal to 66 to each square in a grid of 6×66 \times 6 squares. For a pair of integers (i,j)(i, j) with 1i,j61 \le i, j \le 6, denote by iji \diamond j the integer put into the square located on ii-th row and jj-th column after an operation. How many different operations are there which satisfy the following 2 conditions?

* For every ii (1i61 \le i \le 6), ii=ii \diamond i = i holds.
* For every choice of i,j,k,i, j, k, \ell with 1i,j,k,61 \le i, j, k, \ell \le 6, (ij)(k)=i(i \diamond j) \diamond (k \diamond \ell) = i \diamond \ell holds.

Solution

First, we consider how we can obtain an operation that satisfies the two conditions of the problem. Let us begin with the following Lemma:
Lemma 1: For every pair of integers ii and jj with 1i,j61 \le i, j \le 6, iji \diamond j is the only integer which appears in both ii-th row and jj-th column.
Proof of Lemma 1: It is clear that the number iji \diamond j appears in both ii-th row and jj-th column. Suppose now that for some pair of integers jj', ii' both lying in between 11 and 66, some integer kk appears in both the square located on ii-th row and jj-th column and the square located on ii'-th row and jj-th column, then we have kk=(ij)(ij)=ijk \diamond k = (i \diamond j')(i' \diamond j) = i \diamond j, which implies that iji \diamond j is the only number that can appear in both ii-th row and jj-th column.

Next, we note that since for any choice of positive integers i,j,ki, j, k lying in between 11 and 66 the identity
ik=(ij)(kk)k i \diamond k = (i \diamond j) \diamond (k \diamond k) \diamond k
holds, we see that distribution of numbers in ii-th row and (ij)(i \diamond j)-th row must coincide. Consequently, for any pair of numbers i1,i2i_1, i_2 lying in between 11 and 66, no pair j1,j2j_1, j_2 exists for which i1j1=i2j2i_1 \diamond j_1 = i_2 \diamond j_2, if the distribution of numbers in i1i_1-th and i2i_2-th rows are different. In other words, for any pair of rows the distributions of integers in them either coincide or there exists no integer which appears in both rows.

On the other hand, for any integer ii lying in between 11 and 66, ii=ii \diamond i = i holds; therefore, in ii-th row number ii appears at least once. In view of this fact and the fact mentioned above, we can conclude that the set {1,2,,6}\{1, 2, \dots, 6\} of positive integers is partitioned into the collection I1,I2,,ImI_1, I_2, \dots, I_m, (where mm is a positive integer 6\le 6), of non-empty subsets, which satisfies the following condition:
For any x{1,2,,m}x \in \{1, 2, \dots, m\} and for any iIxi \in I_x, the set IxI_x coincides with the set of all numbers appearing in ii-th row.

By considering columns instead of rows, we can also obtain the following:
The set {1,2,,6}\{1, 2, \dots, 6\} of positive integers is partitioned into the collection J1,J2,,JnJ_1, J_2, \dots, J_n, (where nn is a positive integer 6\le 6), of non-empty subsets, which satisfies the following condition:
For any y{1,2,,n}y \in \{1, 2, \dots, n\} and for any jJyj \in J_y, the set JyJ_y coincides with the set of all numbers appearing in jj-th column.

From Lemma 1 it follows that for any pair of numbers x,yx, y with 1xm1 \le x \le m and 1yn1 \le y \le n, there is a unique integer belonging to the set IxJyI_x \cap J_y. Denote this integer by (x,y)(x, y). Then we can show the following:
Lemma 2: For any choice of x1,x2,y1,y2x_1, x_2, y_1, y_2, (x1,y1)(x2,y2)=(x1,y2)(x_1, y_1) \diamond (x_2, y_2) = (x_1, y_2).
Proof of Lemma 2: First, we note that for any pair iIx,jJyi \in I_x, j \in J_y, (x,y)=ij(x, y) = i \diamond j holds. Therefore, we see that for i1Ix1,i2Ix2,j1Jy1,j2Jy2i_1 \in I_{x_1}, i_2 \in I_{x_2}, j_1 \in J_{y_1}, j_2 \in J_{y_2}, we have
x1,y1x2,y2=(i1j1)(i2j2)=i1j2=x1,y2, \langle x_1, y_1 \rangle \diamond \langle x_2, y_2 \rangle = (i_1 \diamond j_1) \diamond (i_2 \diamond j_2) = i_1 \diamond j_2 = \langle x_1, y_2 \rangle,
proving the Lemma.

Now, since both I1,I2,,ImI_1, I_2, \dots, I_m and J1,J2,,JnJ_1, J_2, \dots, J_n are partitions of the set {1,2,,6}\{1, 2, \dots, 6\}, we see that in the enumeration
()1,1,1,2,,1,n,2,1,2,2,,2,n,m,1,m,2,m,n, (\dagger) \quad \langle 1, 1 \rangle, \langle 1, 2 \rangle, \dots, \langle 1, n \rangle, \langle 2, 1 \rangle, \langle 2, 2 \rangle, \dots, \langle 2, n \rangle, \dots \dots \langle m, 1 \rangle, \langle m, 2 \rangle, \dots \langle m, n \rangle,

Lemma 3: When positive integers m,nm, n satisfying mn=6mn = 6 and enumeration (\dagger) above of the numbers 1,2,...,61, 2, ..., 6 are given, assignment of numbers into squares to satisfy the statement of Lemma 2 is uniquely determined, and this assignment satisfies the conditions of the problem.
Proof of Lemma 3: First, we note that the two conditions of the problem can be stated in terms of x,y\langle x, y \rangle as follows:
x,yx,y=x,y \bullet \quad \langle x, y \rangle \diamond \langle x, y \rangle = \langle x, y \rangle
(x1,y1x2,y2)(x3,y3x4,y4)=x1,y2x3,y4=x1,y4=x1,y1x4,y4. \bullet \quad (\langle x_1, y_1 \rangle \diamond \langle x_2, y_2 \rangle) \diamond (\langle x_3, y_3 \rangle \diamond \langle x_4, y_4 \rangle) = \langle x_1, y_2 \rangle \diamond \langle x_3, y_4 \rangle = \langle x_1, y_4 \rangle \\ = \langle x_1, y_1 \rangle \diamond \langle x_4, y_4 \rangle.
Since for each ii lying in between 11 and 66, there is a unique pair xx and yy for which i=x,yi = \langle x, y \rangle, we see that the claim of Lemma 3 is valid.

Now if we consider an assignment of numbers satisfying the conditions of the problem, then there are m!n!m! \cdot n! enumeration (\dagger)'s giving this assignment corresponding to the number of permutations of sets I1,I2,,ImI_1, I_2, \dots, I_m and J1,J2,,JnJ_1, J_2, \dots, J_n. For each pair m,nm, n satisfying mn=6mn = 6 there are 6!6! different (\dagger)'s, and therefore, the number of ways of assignments satisfying the conditions of the problem is 6!m!n!\frac{6!}{m!n!}, which yields
6!1!6!+6!2!3!+6!3!2!+6!6!1!=122 \frac{6!}{1! \cdot 6!} + \frac{6!}{2! \cdot 3!} + \frac{6!}{3! \cdot 2!} + \frac{6!}{6! \cdot 1!} = 122

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 and solution reproduced as published; topic and difficulty added by this site.