В городе N ровно 300 автомобилей номера которых 100, 101,..., 399 соответственно. Также в этом городе 50 стоянок, которые пронумерованы 00, 01, 02, ..., 49. Машина ,X может припарковаться на стоянку Y тогда и тольк тогда, когда из номера этой машины X можно получить номер стоянки Y путём вычеркивания одной цифры. Все ли машины могут припарковаться на стоянки?
Ответы
Ответ:
Пошаговое объяснение:
Да, все машины могут припарковаться на стоянки.
Заметим, что для каждой стоянки номера машин, которые могут на неё припарковаться, имеют одинаковое количество цифр. Кроме того, для любой пары номеров машин, которые отличаются только одной цифрой, их номера при парковке будут отличаться также только одной цифрой.
Таким образом, можно разбить все номера машин на 10 групп, в каждой из которых будут находиться номера машин, отличающиеся только одной цифрой. Для каждой группы номеров машин можно найти все стоянки, на которые они могут припарковаться, и заметить, что каждая стоянка будет участвовать в ровно двух группах. Это значит, что каждая стоянка может принять ровно 2 номера машин из каждой группы, а значит, всего на каждую стоянку может припарковаться не более 2*10 = 20 машин.
Таким образом, общее количество мест на стоянках равно 50*20 = 1000, что достаточно для парковки всех 300 машин.