Решение во втором случае.
Показать скрытый текст Как и в первом случае:
Существует А = Х!/((Х-(К+1))! * (К+1)!) сочетаний К+1 карты из Х карт
Существует В = Х!/(Х-К)! * К!) сочетаний К карт из Х карт.
Но кроме того, поскольку можно можно пользоваться порядком следования карт, то эти показанные К карт (из К+1) можно представить К! способами
Отсюда равенство имеет вид: А = В * К!
О чём говорит это равенство?
О том, что каждое из А сочетаний (К+1) из Х можно однозначно представить одним из В сочетаний К из Х, предсталенное одним порядком из К! порядков.
То есть:
Х!/((Х-(К+1))!*(К+1)!) = (Х!/((Х-К)! * К!))*К!.
В правой части К! сокращается и мы получаем (Х-(К+1))!*(К+1)! = (Х-К)!
(Х-К)! = (Х-(К+1))!*(Х-К), т.е. (Х-(К+1))!*(К+1)! = (Х-(К+1))! * (Х-К)
Отсюда: (К+1)! = Х-К, или: Х = (К+1)! + К
При К=4 имеем Х = 5! + 4 = 124
Конечно закодировать вручную 124 карты - жизни не хватит, но комп это может сделать.
Я вручную это сделал для К=2.
При К = 2 получается Х = 8 и эти 8 карт я кодировал почти день...
К сожалению, это еще не доказательство, а только оценка сверху. Нам ведь подойдет не любое соответствие между размещениями из 124 по 4 и сочетаниями из 124 по 5, а только такое, в котором каждому размещению соответствует сочетание, включающее все 4 карты, вошедшие в размещение. Не очевидно, что такое соответствие существует (хотя интуиция подсказывает, что должно).
Впрочем, кажется, всё в порядке. Для каждого размещения есть 120 подходящих сочетаний, а для каждого сочетания — 120 размещений. А есть известный результат, что всегда можно получить соответствие, даже если бы было всего по 2 кандидата (кстати неплохая задачка, она уже предлагалась здесь?).
Резонное замечание. Тем не менее могу предложить алгоритм заполнения.
Рассортируем все сочетания 4-х из 124: 1-2-3-4, 1-2-3-5, 1-2-3-6,..., 1-2-3-124, 1-2-4-5,... и т.д.
Каждому из таких сочетаний мы должны выделить единственную из оставшихся 120 карт.
Запишем все 120 (отсортированных) оставшихся номеров для каждого сочетания 4 из 124.
Для 1-2-3-4 это будет: 5,6,7,...124, для 1-2-3-5 это будет 4,6,7,...,124 и т.д.
И начнем присваивать, придерживаясь следующих правил:
1)Каждому очередному сочетанию выделим первый из непомеченных номеров. Например для 1-2-3-4 это будет 5. То есть сочетанию 4 из 124 1-2-3-4 поставим в соответсвие сочетание 5 из 124 - 1-2-3-4-5. Пометим его плюсом (+)
2) Заметим при этом, что сочетанию 1-2-3-4-5 могли бы соответствовать кроме 1-2-3-4 ещё 4 сочетания: 1-2-3-5, 1-2-4-5, 1-3-4-5 и 2-3-4-5, но мы выбрали только одно - 1-2-3-4 и остальные должны пометить как запрещённые - мы будем помечать соответствующие номера в соответствующих сочетаниях: для 1-2-3-5 это будет 4, для 1-2-4-5 -> 3, для 1-3-4-5 -> 2, для 2-3-4-5 -> 1 минусом (-)
3) После того, как мы такой номер выделили и зачеркнули все порождённые запрещённые, мы переходим к следующему сочетанию.
В данном случае после 1-2-3-4 идёт 1-2-3-5 со списком номеров 4(-),6,7,...,124.
Поскольку 4 помечено, выбираем 6, помечаем его (+) и помечаем (-): 1-2-3-6: 5, 1-2-5-6: 3, 1-3-5-6: 2 и 2-3-5-6: 1.
Таким образом, дойдя до конца первый раз, мы получим для каждого сочетания один (+) и четыре (-).
Таким образом за один проход мы выбрали одно сочетание 5 из 124 для одного сочетания 4 из 124.
Нам осталось пройти так ещё 23 раза (одно сочетание 4 из 124 благодаря 4!=24 перестановкам позволяет выбрать 24 сочетания 5 из 124).
На каждом проходе каждое сочетание 4 из 124 будет получать в своём списке номеров один + и четыре -.
Всего список номеров для каждого сочетания содержит 120 номеров, каждый проход забирает 5 номеров, всего 24 прохода как раз хватит.