niktoinikak (niktoinikak) wrote,
niktoinikak
niktoinikak

Предыдущая задача о школьникак и задачах

https://niktoinikak.livejournal.com/1573785.html
допускает довольно широкое обобщение, также имхо красивое и интересное.

20 сортов пирожных по 10 пирожных каждого сорта упакованы в 20 ящиков по 10 пирожных в каждом. Доказать, что при любой такой раскладке всегда можно выбрать 20 пирожных двадцати различных сортов, выбрав по одному пирожному из каждого ящика.

Решение.
[Spoiler (click to open)]Действуем индукцией по числу К пирожных каждого сорта. Если К = 2 то это предыдущая задача(ну или - решается также).

Пусть теперь К > 2

Покажем, что если распределение пирожных таково, что искомый выбор возможен, то переложив местами любые 2 пирожных получим распределение, в котором также можно выбрать искомую "линию" - по одному пирожному каждого сорта взяв одно пирожное из каждого ящика.
Т к одно такое распределение всегда есть, и любое можно получить из любого другого последовательными перекладываниями, задача будет решена.
Итак, имеем укладку, в которой можно выбрать "линию". Убрав эту линию, получаем ту же задачу, но для К-1. В которой опять можно выбрать линию по предположению индукции! И т д - т е получаем для нашей раскладки набор из К линий! Теперь поменяв местами 2 пирожных видим, что мы задели максимум 2 линии - а их у нас больше двух! Т е остаётся нетронутая линия! Всё.
Восклицательные знаки - мой восторг :-)
Tags: Математика, вечное
Subscribe

  • И снова о русофобии.

    В основном она конечно - как и должно (об этом чуть позже) - чисто русское явление. Встретил у сапожника(точнее, у Мелихова) цитаты. "самородки из…

  • Читательское

    Поскольку отвращение есть чувство, Испытываемое мной всегда При наблюденье за людьми, искусство Мне часто неприятно, это да. Поскольку…

  • Счастье

    Я счастье наконец обрел, оплот ища, Уже привычны, недругам назло, И звездно-полосатые полотнища, И волн морских январское тепло. Но, вопреки…

promo niktoinikak december 8, 2016 21:29 1
Buy for 10 tokens
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments