где тут принцип Дирихле

[dp]

Задача: В магазине «Всё для путешествий» продаются 20 плееров по цене от 500 до 800 рублей и 20 наушников по цене от 50 до 140 рублей. Известно, что любой один предмет стоит целое число рублей и никакие два не стоят одинаково. Докажите, что два покупателя смогут приобрести по одному плееру с наушниками, потратив одинаковое количество денег.

Решение: Заметим, что всего различных ценников в магазине может быть (800 – 500 + 1) + (140 – 50 + 1) = 392. А всевозможных пар «плеер-наушники» – 20*20 = 400. Значит, по принципу Дирихле, найдутся две разные пары с одинаковой суммарной стоимостью. Однако, если в этих парах какой-то предмет будет одним и тем же, то оставшиеся предметы стоят поровну, поэтому тоже одинаковые. Следовательно, найдутся две пары,
которые смогут купить два разных покупателя.

Недоумение: Никак не пойму причем тут - "Значит, по принципу Дирихле, найдутся две разные пары с одинаковой суммарной стоимостью." С какой стати? Взяли просто кол-о ценников. При этом смешав ценники мы можем выбрать как два плеера, так и два наушника. И даже общее кол-во ценников меньше чем число возможных пар. Правильное ли тут доказательство?

[TOTAL]

Решение
Суммарная стоимость какой-то пары «плеер-наушники» равна $i+j, \quad i=500, \dots, 800, \quad j=50, \dots, 140$, т.е суммарная стоимость может принимать $392$ различных значения. (Точнее, $391$.) А различных пар «плеер-наушники» - $400$. Значит, по принципу Дирихле, найдутся две разные пары с одинаковой суммарной стоимостью.

Осталось недоумение?

[warlock66613]

dp в сообщении #1386060 писал(а):

Правильное ли тут доказательство?

Идея правильная, насчёт деталей (максимального количества цен и способа его подсчёта) не уверен. А идея следующая.

dp в сообщении #1386060 писал(а):

При этом смешав ценники мы можем выбрать как два плеера, так и два наушника.

Нет, никто ничего не смешивает. Считаем, что продажи идут комплектами "плеер + наушники". Количество возможных цен на такие комплекты не превышает разности максимальной цены ($800 + 140$) и минимальной ($500 + 50$), ну и плюс $1$. Итого максимум $391$ цена. Различных же комплектов $400$. Теперь цены - это клетки, комплекты - это кролики, которых мы рассаживаем по клеткам, и поскольку количество кроликов превышает количество клеток, то по принципу Дирихле найдётся клетка с двумя кроликами - то есть два комплекта с одной и той же ценой.

[dp]

TOTAL в сообщении #1386078 писал(а):

Суммарная стоимость какой-то пары «плеер-наушники» равна $i+j, \quad i=500, \dots, 800, \quad j=50, \dots, 140$, т.е суммарная стоимость может принимать $392$ различных значения

из такого объяснения неочевидно, тут надо еще доказывать почему будет 391-но значение

а вот тут понятно:

warlock66613 в сообщении #1386079 писал(а):

Количество возможных цен на такие комплекты не превышает разности максимальной цены ($800 + 140$) и минимальной ($500 + 50$)

спасибо

[Someone]

dp в сообщении #1386122 писал(а):

из такого объяснения неочевидно, тут надо еще доказывать почему будет 391-но значение

Вам нужно построить мостик длиной 7 метров, имея 7 метровых плит. Каждая плита должна опираться на две опоры, но две соприкасающиеся плиты опираются соприкасающимися концами на одну опору. Сколько нужно опор?