Арифметическая задача прямо из жизни

[Ktina]

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

[VoloCh]

43?

[nnosipov]

Здесь может быть полезным вот такое утверждение: при взаимно простых $A>1$ и $B>1$ наибольшее натуральное число, не представимое в форме $Ax+By$, где $x$, $y$ --- неотрицательные целые числа, равно $AB-A-B$.

[neo66]

39

[nnosipov]

neo66 в сообщении #584832 писал(а):

39

43 нельзя представить в виде $6x+9y+20z$, где $x$, $y$, $z$ --- неотрицательные целые числа. А все целые $>43$ --- можно.

[maxal]

см. http://en.wikipedia.org/wiki/Frobenius_number

[Dave]

nnosipov в сообщении #584795 писал(а):

Здесь может быть полезным вот такое утверждение: при взаимно простых $A>1$ и $B>1$ наибольшее натуральное число, не представимое в форме $Ax+By$, где $x$, $y$ --- неотрицательные целые числа, равно $AB-A-B$.

Доказательство (так, на всякий случай). Если $AB-A-B=Ax+By$, то $A(B-x-1)=B(y+1)$, и из взаимной простоты $A$ и $B$ следует, что $y+1$ делится на $A$, а $B-x-1$, а значит и $x+1$, делится на $B$. При неотрицательных $x$ и $y$ это возможно только при $x \geqslant B-1$ и $y \geqslant A-1$, но тогда $Ax+By \geqslant A(B-1)+B(A-1)=2AB-A-B>AB-A-B$, значит $AB-A-B$ не представимо в указанном виде.
С другой стороны, если $z>AB-A-B$, то т.к. числа $Ax$, $x=0,1,\ldots,B-1$ дают $B$ попарно-различных остатков при делении на $B$, то найдётся такое $x$ из указанного диапазона, что $Ax \equiv z \pmod B$, т.е. $z-Ax=By$ для некоторого целого $y$. Осталось доказать, что $y \geqslant 0$. Но это действительно так, ибо $y=\frac {z-AX} B>\frac {AB-A-B-A(B-1)} B=-1$. $\blacksquare$

[neo66]

nnosipov в сообщении #584795 писал(а):

Здесь может быть полезным вот такое утверждение: при взаимно простых $A>1$ и $B>1$ наибольшее натуральное число, не представимое в форме $Ax+By$, где $x$, $y$ --- неотрицательные целые числа, равно $AB-A-B$.

Не обратил внимания на слова "при взаимно простых". Никому нельзя верить, в особенности себе.

[Dave]

Также верно (впервые доказано Сильвестром), что

В случае взаимно-простых $A>1$ и $B>1$ количество натуральных чисел, непредставимых в виде $Ax+By$, где $x$ и $y$ - неотрицательные целые числа, в точности равно $\frac {(A-1)(B-1)} 2$.

Доказательство. Пусть $P=AB-A-B=(A-1)(B-1)-1$. Как было доказано ранее, все непредставимые числа находятся в диапазоне от $1$ до $P$, причём $P$ - непредставимое число. Рассмотрим множество $V$ значений, которые может принимать функция $f(x,y)=Ax+By$ при $x=0,1,\ldots,B-2$ и $y=0,1,\ldots,A-2$. Все такие значения попарно различны, т.к. если $Ax_1+By_1=Ax_2+By_2$, то $A(x_1-x_2)=B(y_2-y_1)$ и $x_1-x_2$ должно делиться на $B$, что, учитывая $-(B-2) \leqslant x_1-x_2 \leqslant B-2$, возможно только при $x_1-x_2=0$ и значит $y_2-y_1=0$. Итак, в $V$ ровно $(A-1)(B-1)=P+1$ элемент.
С другой стороны, если неотрицательное целое число $z<P$ представимо в виде $Ax+By$ для неотрицательных целых $x$ и $y$, то $x=\frac {z-By} A<\frac {AB-A-B} A<B-1$ и $y=\frac {z-Ax} B<\frac {AB-A-B} B<A-1$, т.е. $z \in V$.
И, наконец, заметим, что какова бы ни была пара $(x,y)$ из рассматриваемого выше диапазона, пара $(B-2-x,A-2-y)$ также принадлежит этому диапазону и не совпадает с ней, т.к. минимум одно из чисел $A$ и $B$ (а значит и $A-2$ и $B-2$) нечётно. Но

$$f(B-2-x,A-2-y)=A(B-2-x)+B(A-2-y)=2(AB-A-B)-(Ax+By)=2P-f(x,y),$$

значит ровно одно из чисел $f(x,y)$ и $f(B-2,A-2)$ меньше $P$, а другое больше $P$.
Итак, $V$ указанным выше образом разбивается на пары и в каждой паре ровно одно число меньше $P$. Это означает, что среди чисел $0,1,\ldots,P-1$ представимых ровно $\frac {P+1} 2$, а непредставимых $P-\frac {P+1} 2$. Добавляя наибольшее непредставимое число $P$, получим количество $P+1-\frac {P+1} 2=\frac {P+1} 2$. $\blacksquare$

[nnosipov]

А я добавлю вот такое утверждение. Пусть $a$, $b$, $c$ --- натуральные числа, и пусть ни одно из них не делит никакое другое. Тогда все натуральные числа, начиная с $M=\mbox{НОД}(a,b)c+\mbox{НОК}(a,b)-a-b-c+1$, представляются в виде $ax+by+cz$, где $x$, $y$, $z$ --- неотрицательные целые числа. При $a=6$, $b=9$, $c=20$ получаем $M=44$, и нам остаётся только проверить, что число $43$ не допускает нужного представления.

И ещё одно добавление: если $a=kl$, $b=lm$, $c=mk$, где $k$, $l$, $m$ --- попарно взаимно простые числа $>1$, то указанное выше число $M$ будет наименьшим числом с таким свойством.