Ресторан МайМональдс продаёт цыплячьи ножки в упаковках по 6, 9 или 20 штук.
Какое наибольшее целое число ножек я НЕ могу купить в этом ресторане?

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999..........8

ну или чуть больше

(1)9+9=18

(2) А 21 чем не подходит?

43

(3)25>21

7n

(3) 9+6+6

(4)+1

(3)6+6+9 =21

(4)51
?

(10)+упс, сорри, после (9) ясно, что не прав.

(10) 9+9+9+9+9+6

(0) нужно дополнительное услосие, иначе ответ (1) правильный - нет такого количества, которое ты не мог бы купить

Чуть не сказал про наименьшее кратное, но успел подумать :)

Только перебором такое счиается? Что-то про линейное программирование припоминается, но очень смутно.

(13) есть такое количество, например, в (4)

(0) 5

(14)Комбинаторика, я думаю.

(16) Наибольшее число.

сорок три

кстати, (4) - есть доказательство максимальности?

28

(4) +1
43, если больше то
любое число вида x3 это a*9+b*6
любое число вида x3+2 это 20+a*9+b*6  
любое число вида x3+1 это 40+a*9+b*6

(22) ну это еще доказывать надо

Одну, вот тут обяснение http://prukol.com/?p=2776

Получилось 43

48 вроде не купишь

(26) да легко 6*8

а, нет, запросто 30+18

(26) см (22)

(20) есть конечно, не мое правда.

(23) это задачи математических олимпиад 5-7й класс,
лениво раписывать, можно просто добавить фразу "очевидно, что"

а 43 как находится?

(31) я к тому, что если в условии числа поменяю, то как быстро найдется решение? Есть общий алгоритм?

(33) Так ты меняй и посмотрим )

(27) ну значит 49... Ни на 6, ни на 9, ни на 20 не делится.
Чем не устраивает ответ в 1?

(34) 11, 17, 27

(35) 49 = 20*2+9

(37) вон оно чо :)

(1) 999...9998 = 999...9900+98
первое делится на 9, второе 98=49*2 и (37)

(36) 65

(40) ты че там переборный алгоритм написал?

(41) Формулу.

(42) в студию ))

(43) Рано.. нужны еще опыты..

(36) 5048

(40) брешишь: 65 = 2*27+11

54

(46) Хм.. я ж говорю, опыты нужны.

(45) Че это )

(49) наименьшее общее кратное -1,
но похоже лажа (для 2 чисел бы сработало, наверное)

(36) 47?

(36) 25502501

(33) чего-то типа минимальный элемент не входящий в абелеву группу порожденную {x,y,z...} mod НОК (x,y,z)

67

(50) ну для двух есть точная формула А*Б-А-Б

простое решение есть? или опять 10 листов матана ?

(56) простого нет, сложного тоже - перебор пока есть

(55) а для трех наверное а*в*с-а*в-а*с-в*с-а-в-с?

(58) для трех не может быть больше чем для 2-х
(55) значит берем 11*17-11-17 и перебираем вниз

(55) а доказательство этой формулы есть?

(55) 2 и 4, например

может 43?

(61) 2 и 4 не подходят наверное потому что 4 =2+2

(55) а как для для пары 6 и 9 из первого примера мы получили
43 > 39=6*9-6-9
не работает формула

(64) Для пары 6 и 9 решения вообще нет.

(65) согласен, числа должны быть взаимнопростыми

+(66) точно

(60) копаться надо

Ключевые слова по сабжу:
McNugget Number
Frobenius Number
Frobenius Equation
Coin Problem

проверил перебором получил 43

(60) А, Б - взаимно просты; пусть 1 < А < Б, тогда (А-2)*Б < А*Б-А-Б < А*Б-А-Б+1 < (А-1)*Б

Рассмотрим множество чисел М вида 1*Б, 2*Б, ..., (А-2)*Б, (А-1)*Б
Факт 1. Среди чисел из М ни одно не имеет остатка от деления на А равного 0
Факт 2. Среди чисел из М нет пары различных, имеющих одинаковый остаток при делении на А
То есть М содержит все ненулевые остатки при делении на А и ровно по одному разу

Пусть А*Б-А-Б = К1*А+К2*Б, тогда из неравенств первой строки К2 < А-1
Слева остаток от деления на А равен (-Б), справа К2*Б, но в М остаток (-Б) имеет только (А-1)*Б, но К2 < А-1 - следовательно получить такое число нельзя

Докажем, что это максимальное число
Факт 3. Если Т+1, Т+2, ..., Т+А - можно получить, то можно получить вообще любое число большее Т

В качестве Т возьмем А*Б-А-Б и покажем, что любое из А*Б-А-Б+1, ..., А*Б-А-Б+А=А*Б-Б можно получить
Среди этих чисел есть абсолютно все остатки при делении на А ровно по разу, значит ПОЧТИ каждое из них можно представить в виде К1*А+К2*Б, где 1 < К2 < А-1 (слагаемое К2*Б это элемент из М кроме (А-1)*Б)

в это ПОЧТИ не укладывается два остатка:
1. остаток равен 0, но его можно представить в виде К1*А
2. остаток равен -Б, но такой остаток имеет член (А-1)*Б, который делится на Б

Следовательно все большие А*Б-А-Б представить можно

(71) Разве ключевые слова в (69) не по теме?
Например: http://www.iam.khv.ru/articles/Ustinov/nth32.pdf

(72)
1. хотелось самому вывести
2. та ссылка все же для более сложных случаев, а это еще 19 век

43

(0) 39

(75) 6+6+6+6+6+9

(54) 20 * 2 + 9 * 3

(45) 20 * 244 + 9 * 18 + 6 * 1

(75) раз'банили что ли?

(52) 20 * 1275121 + 9 * 9

(0) 2 в степени 20 996 001 минус единица

(80) Это для 11, 17, 27

Путем перебора мною было установлено, что от 0 до 200 максимум нельзя купить 43 ножки. Теперь остается доказать, что больше 200 ножек купить нельзя.

(1.)

<Количество ножек> = <произвольное количество ножек в пакетах по 20> +
<произвольное число ножек от 44 до 200>

Оба слагаемых в правой части ОДНОЗНАЧНО можно купить => можно купить <Количество ножек> в левой части в пачках 6, 9 и 20.

Вопросы?

(83) см. 22

см. (22)

(85) Пардон, хотел ДОКАЗАТЬ что больше 43 можно купить любое число и написал, что что можно.

Запутался

А так  - 43

Исправленное доказательство:

Путем перебора было установлено, что от 0 до 200 максимум нельзя купить 43 ножки. Теперь остается доказать, что больше 200 ножек купить можно.

(1.)

<Количество ножек> = <произвольное количество ножек в пакетах по 20> +
<произвольное число ножек от 44 до 200>

Любое число больше 200 можно представить в виде суммы (1.). Оба слагаемых в правой части суммы ОДНОЗНАЧНО можно купить => можно купить <Количество ножек> в левой части в пачках 6, 9 и 20.

Итак, больше 43 ножек купить нельзя.

(85) А так?

>больше 43 ножек купить нельзя.
т.е. Можно

В (22) написано элементарное доказательство того, что больше 43 ножек купить нельзя.

Точнее что любое количество больше 43 купить можно :)

(91) А это ещё один вариант доказательства :-), более "эмпиричный", чтоли. (92) (89) Мы уже запутались в этих формулировках, как в макаронах.

Самый тяжелый случай при остатке 1.
a*9+b*6 дает любое кратное трем начиная с шести.
40+6=46, то есть 43 мы не можем представить, а 46 уже можем.

Будь мужиком, купи бедрышки...