Maths Olympiad Prep

Library / /79 of 86

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Estonia

Juku has the first 100 volumes of the Harrie Totter book series at his home. For every ii and jj, where 1i<j1001 \le i < j \le 100, call the pair (i,j)(i, j) reversed if volume No jj is before volume No ii on Juku's shelf. Juku wants to arrange all volumes of the series to one row on his shelf in such a way that there does not exist numbers i,j,ki, j, k, where 1i<j<k1001 \le i < j < k \le 100, such that pairs (i,j)(i, j) and (j,k)(j, k) are both reversed. Find the largest number of reversed pairs that can occur under this condition.

Solutions — 2

Solution 1

Let all 100 volumes be placed to a shelf aa in some order. For every i=1,2,...,100i = 1, 2, ..., 100, let aia_i be the number of the volume that occurs as the iith in this order. In the order the volumes occur on shelf aa, we start relocating the volumes to two new shelves bb and cc. We place a volume to the end of shelf bb if, as the intermediate result, all volumes on shelf bb would be increasingly sorted by volume numbers. Otherwise, we place the volume to the end of shelf cc if, as the intermediate result, all volumes on shelf cc would be increasingly sorted by volume numbers. Continuing this way, we either can relocate all volumes onto two shelves in such a way that all volumes on either shelf are increasingly sorted by volume numbers or get stuck on some step kk of the process because aka_k is less than the number of the last volume on both new shelves. In the last case, let the number of the last volume on shelf cc be aja_j; then, by assumptions, j<kj < k and aj>aka_j > a_k. Since volume No aja_j has been relocated to shelf cc, some volume with number aia_i must occur on shelf bb such that i<ji < j and ai>aja_i > a_j. This means that pairs (i,j)(i, j) and (j,k)(j, k) were initially reversed. Hence we can conclude that, in the case of Juku's favourite orderings, all volumes can be relocated to two shelves, i.e, there exist two tuples ai1,ai2,...,aisa_{i_1}, a_{i_2}, ..., a_{i_s} and aj1,aj2,...,ajta_{j_1}, a_{j_2}, ..., a_{j_t} with s+t=100s + t = 100, where i1<...<isi_1 < ... < i_s, ai1<...<aisa_{i_1} < ... < a_{i_s} and j1<...<jtj_1 < ... < j_t, aj1<...<ajta_{j_1} < ... < a_{j_t}. The number of pairs (i,j)(i, j) such that i<ji < j and the numbers aia_i and aja_j are in distinct tuples is exactly stst. Each reversed pair (i,j)(i, j) must be one of these stst pairs. Thus the number of reversed pairs does not exceed stst. As st(s+t2)2=502=2500st \le (\frac{s+t}{2})^2 = 50^2 = 2500, the number of reversed pairs cannot exceed 2500. The number 2500 is achieved by the order 51,52,...,100,1,2,...,5051, 52, ..., 100, 1, 2, ..., 50.

Solution 2

Let all 100 volumes be placed to the shelf in some order. Consider the graph whose vertices are numbers 1,2,...,1001, 2, ..., 100 and an edge occurs between vertices ii and jj if and only if either (i,j)(i, j) or (j,i)(j, i) (depending on whether i<ji < j or j<ij < i) is reversed. Suppose that the graph contains an odd cycle. Such cycle must contain three consecutive vertices i,ji, j and kk that are in either increasing or decreasing order; w.l.o.g., assume that i<j<ki < j < k. Then pairs (i,j)(i, j) and (j,k)(j, k) are both reversed. Thus under the conditions of the problem, the graph cannot contain an odd cycle. Hence the graph is bipartite. Let the numbers of vertices in the two parts be ss and tt, respectively; then the maximal number of edges is stst. By AM-GM, st(s+t2)2=502=2500st \le (\frac{s+t}{2})^2 = 50^2 = 2500. If the volumes are in the order 51,52,...,100,1,2,...,5051, 52, ..., 100, 1, 2, ..., 50, exactly 2500 reversed pairs arise indeed.

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.