Maths Olympiad Prep

Library / Japan Mathematical Olympiad Initial Round /6 of 7

Japan Mathematical Olympiad Initial Round

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 1≤i,j≤61 \le i, j \le 6, denote by i⋄ji \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 (1≤i≤61 \le i \le 6), i⋄i=ii \diamond i = i holds.
* For every choice of i,j,k,ℓi, j, k, \ell with 1≤i,j,k,ℓ≤61 \le i, j, k, \ell \le 6, (i⋄j)⋄(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 1≤i,j≤61 \le i, j \le 6, i⋄ji \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 i⋄ji \diamond j appears in both ii-th row and jj-th column. Suppose now that for some pair of integers j′j', i′i' 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 i′i'-th row and jj-th column, then we have k⋄k=(i⋄j′)(i′⋄j)=i⋄jk \diamond k = (i \diamond j')(i' \diamond j) = i \diamond j, which implies that i⋄ji \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
i⋄k=(i⋄j)⋄(k⋄k)⋄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 (i⋄j)(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 i1⋄j1=i2⋄j2i_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, i⋄i=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 i∈Ixi \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 j∈Jyj \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 1≤x≤m1 \le x \le m and 1≤y≤n1 \le y \le n, there is a unique integer belonging to the set Ix∩JyI_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 i∈Ix,j∈Jyi \in I_x, j \in J_y, (x,y)=i⋄j(x, y) = i \diamond j holds. Therefore, we see that for i1∈Ix1,i2∈Ix2,j1∈Jy1,j2∈Jy2i_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,y1⟩⋄⟨x2,y2⟩=(i1⋄j1)⋄(i2⋄j2)=i1⋄j2=⟨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,y⟩⋄⟨x,y⟩=⟨x,y⟩ \bullet \quad \langle x, y \rangle \diamond \langle x, y \rangle = \langle x, y \rangle
∙(⟨x1,y1⟩⋄⟨x2,y2⟩)⋄(⟨x3,y3⟩⋄⟨x4,y4⟩)=⟨x1,y2⟩⋄⟨x3,y4⟩=⟨x1,y4⟩=⟨x1,y1⟩⋄⟨x4,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,y⟩i = \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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