MathDB
ASU 246 All Soviet Union MO 1977 1000 and 1000 boxes all numbered

Source:

July 6, 2019
combinatoricsImpossible

Problem Statement

There are 10001000 tickets with the numbers 000,001,...,999000, 001, ... , 999, and 100100 boxes with the numbers 00,01,...,9900, 01, ... , 99. You may put a ticket in a box, if you can obtain the box number from the ticket number by deleting one digit. Prove that:
a) You can put all the tickets in 5050 boxes;
b) 4040 boxes is not enough for that;
c) it is impossible to use less than 5050 boxes.
d) Consider 1000010000 44-digit tickets, and you are allowed to delete two digits. Prove that 3434 boxes is enough for storing all the tickets.
e) What is the minimal used boxes set in the case of kk-digit tickets?
Back to ProblemsView on AoPS