ASU 568 Commonwealth of Independent States 1991 cinema with mxn seats
Source:
August 15, 2019
minimumcombinatorics
Problem Statement
A cinema has its seats arranged in rows columns. It sold mn 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 such that he could have always put every ticket holder in the correct row or column and at least people in the correct seat?