Maths Olympiad Prep

Library / /18 of 19

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Soviet Union

Problem:

A cinema has its seats arranged in nn rows imes imes mm columns. It sold mnmn tickets but sold some seats more than once. The usher managed to allocate seats so that every ticket holder was in the correct row or column. Show that he could have allocated seats so that every ticket holder was in the correct row or column and at least one person was in the correct seat. What is the maximum kk such that he could have always put every ticket holder in the correct row or column and at least kk people in the correct seat?

Solution

Solution:

Suppose it is not possible. Take any person, label him P1P_1. Suppose he should be in seat S1S_1. If seat S1S_1 is vacant, then we can just move him to S1S_1, so S1S_1 must be occupied by someone. Call him P2P_2. Continue, so that we get a sequence P1P_1, P2P_2, P3P_3, ... where PiP_i should be in the seat occupied by Pi+1P_{i + 1}. Since there are only finitely many people, we must get a repetition. Suppose the first repetition is Pi=Pi+jP_i = P_{i + j}. Then we can move PiP_i to Pi+1P_{i + 1}, Pi+2P_{i + 2} to Pi+3P_{i + 3}, ..., Pi+j1P_{i + j - 1} to PiP_i and then these jj people will all be in their correct seats. Contradiction. So it is possible.

Suppose that m+n1m + n - 1 tickets to seat (1,1)(1,1) have been sold and n1n - 1 seats to each of (2,1)(2,1), (3,1)(3,1), ..., (m,1)(m,1). Then to comply with the conditions the people with tickets to (1,1)(1,1) must occupy the whole of the first row and first column. Hence those with tickets to (k,1)(k,1) for k>1k > 1 must occupy the whole of row kk apart from (k,1)(k,1). Thus the seating is completely determined and only one person is in the correct seat - namely the person in (1,1)(1,1).

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 reproduced verbatim; metadata (topic, difficulty) added by this project.