Olympiad Maths Prep

Library / /9 of 14

Combinatorics Difficulty 6.5 National olympiad Prove it Czech Republic

There are 234 visitors in a cinema auditorium. The visitors are sitting in nn rows, where n4n \ge 4, so that each visitor in the ii-th row has exactly jj friends in the jj-th row, for any i,j{1,2,...,n},iji, j \in \{1, 2, ..., n\}, i \neq j. Find all the possible values of nn. (Friendship is supposed to be a symmetric relation.)

Solution

For any k{1,2,...,n}k \in \{1, 2, ..., n\} denote by pkp_k the number of visitors in the kk-th row. The stated condition on given ii and jj implies that the number of friendly pairs (A,B)(A, B), where AA and BB are from the ii-th row and from jj-th row respectively, is equal to the product jpij p_i. Interchanging the indices ii and jj, we conclude that the same number of friendly pairs (A,B)(A, B) equals ipji p_j. Thus jpi=ipjj p_i = i p_j or pi:pj=i:jp_i : p_j = i : j, and therefore, all the numbers pkp_k must be proportional as follows:
p1:p2::pn=1:2::n. p_1 : p_2 : \dots : p_n = 1 : 2 : \dots : n.
Let us show that under this proportionality the visitors can be friendly in such a way which ensures the property under consideration. Thus assume that for some positive integer dd, the equality pk=kdp_k = k d holds with any k{1,2,...,n}k \in \{1, 2, ..., n\}. Let us

start with the case d=1d = 1 when the numbers of visitors in single rows are successively 1,2,...,n1, 2, ..., n. Then the stated property holds true if (and only if) any two visitors — taken from distinct rows in the whole auditorium — are friends. In the case when d>1d > 1, let us divide all the visitors into dd groups G1,G2,...,GdG_1, G_2, ..., G_d so that for arbitrary k=1,2,...,dk = 1, 2, ..., d, the numbers of visitors from the group GkG_k in single rows are successively 1,2,...,n1, 2, ..., n. It is evident that the stated property holds true under the following condition: two visitors are friends if and only if they belong to the same group GkG_k.
It follows from the preceding that our task is to find such integer values of nn, n4n \ge 4, for which there exists a positive integer dd satisfying the equation
d+2d++nd=234ordn(n+1)=468. d + 2d + \dots + n d = 234 \quad \text{or} \quad d n(n+1) = 468.
Thus we look for all divisors 468=223213468 = 2^2 \cdot 3^2 \cdot 13 which are of the form n(n+1)n(n+1). Inequality 2223>46822 \cdot 23 > 468 implies that n<22n < 22 and hence n{4,6,9,12,13,18}n \in \{4, 6, 9, 12, 13, 18\}. It is easy to see that the only satisfactory nn equals 1212 (which corresponds to d=3d=3).

Answer. The unique solution is n=12n = 12.

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.