Задача о расплате без сдачи

[Andrey A]

gris в сообщении #1568575 писал(а):

На небольших банкнотах подтверждается!

Спасибо! Но, вообще говоря, как-то непривычно — такое простое решение должно иметь вполне человеческое объяснение. А тут целая гипотеза ) Купюры, это с легкой руки Doctor Boom пошло. Сойдет для наглядности.

[gris]

Ну количество неудач ровно в два раза меньше максимальной неудачи++. Это тоже не случайно, наверное. Кстати, и по количеству способов оплаты есть статья(?) в OEIS.
Задача вроде бы вполне для семиклассников, ну или постарше, чтобы поучиться индукции. Но сколько для школьников возможностей приобщиться и к диофантовым уравнениям, и к PARI, и к бытовой экономике .

[Andrey A]

Это да. Но под "задачей для семиклассников" Вы, видимо, имели ввиду стартовую. Обобщенная, строго говоря, до сих пор не решена. Или пусть так: имеется решение, требующее доказательств ) Кстати, во вчерашнем посте опечатка:

Andrey A в сообщении #1568518 писал(а):

Всего таких пар $\varphi (n_1,n_2) /2$, где $\varphi ()$ — функция Эйлера.

Правильно так: $\varphi (n_1n_2) /2$, где $\varphi ()$ — функция Эйлера. Теперь это непоправимо.

[Andrey A]

Всё-таки тут нужно объясниться. Доказательство есть, но очень муторное, хотя утверждение простое. Пусть $p \neq q$ — пара простых, $M=pq$ и $a+b=M$, причем $a,b$ вз. просты с $M$ (значит и между собой, $a>0,b>0$). Утверждается, что в натуральных числах разрешимо ровно одно из двух уравнений: $px+qy=a$ либо $px+qy=b$. Доказательство сокрыто в глубине древней темы, в которой и сам теперь не разберусь. Уверен, что можно доказать в две строки, но это, конечно, лень. Важно, что глубоких свойств простых (следствий из малой теоремы Ферма и т.д.) для такого доказательства не требуется, и, значит, простота $p,q$ — требование излишнее, достаточно их взаимной простоты. То же и касательно количества возможных пар $(a,b)$ (если отсеивать из $M$ не любые $\gcd(M,...)>1$, а именно кратные $p,q$). Оно равно $(p-1)(q-1)/2$ при взаимной простоте $p,q$. Остальные разъяснения даны выше.

[RIP]

Проблема Фробениуса

[Andrey A]

RIP в сообщении #1568617 писал(а):

Проблема Фробениуса

Спасибо! Как всегда всё украдено до нас. Или не всё? Формулы количества и наибольшего из непредставимых увидел, а самого способа вычисления пар для фиксированного числа Фробениуса что-то не нашел.
Тут русский перевод, если что https://wiki5.ru/wiki/Coin_problem. Насчет $n=3$ тоже думал, но не знал что открытая проблема. Очень интересно.

[RIP]

Вообще, для двух чисел всё очень просто. Если $a,b$ — взаимно простые натуральные числа, то $ab-a-b$ — наибольшее целое число, не представимое в виде $ax+by$ с целыми $x\geqslant0$, $y\geqslant0$. Более того, для всякого целого $k$ ровно одно из чисел $k,ab-a-b-k$ представимо в таком виде.
1) Непредставимость: если $ab-a-b=ax+by$, то $x\equiv-1\pmod{b}$, $y\equiv-1\pmod{a}$, откуда $ax+by\geqslant a(b-1)+b(a-1)>ab-a-b$.
Поэтому оба числа $k,ab-a-b-k$ в нужном виде представить нельзя.
2) Что касается представимости, то всякое целое число $k$ единственным образом представляется в виде $k=ax+by$ с целыми $x,y$ при условии $0\leqslant x\leqslant b-1$ ($x$ определяется из сравнения $ax\equiv k\pmod{b}$). При этом если $k=ax+by$, то $ab-a-b-k=a(b-1-x)+b(-y-1)$.

[Andrey A]

Да, просто. Но, знаете, хотелось бы еще проще. Всё крутится вокруг двух утверждений. Первое (на котором основывалось мое доказательство) в Вашей терминологии звучит так: оба числа $k,ab-k$ в нужном виде представить нельзя. Но ведь тут совсем просто: если два числа представимы в нужном виде, то представима и их сумма (просто складываем коэффициенты при $a,b$). Тогда получаем неразрешимое в натуральных числах уравнение $ax+by=ab.$ Неразрешимое, поскольку либо $x=0,$ либо $y=0,$ и других решений быть не может. Второе я бы сформулировал так: любое положительное число вида $ab-n(a+b)$ не представимо в нужном виде. Как следствие — ведь $n(a+b)=an+bn$ представимо. Отсюда быстро следует всё остальное.

[RIP]

Andrey A в сообщении #1568705 писал(а):

Второе я бы сформулировал так: любое положительное число вида $ab-n(a+b)$ не представимо в нужном виде.

Это не второе, а банальное следствие первого. Для положительных коэффициентов второе утверждение звучит так: для любого целого $k$ (ровно) одно из чисел $k$, $ab+a+b-k$ имеет вид $ax+by$ с натуральными $x,y$. (Оба не могут быть представимы — это банальность; смысл утверждения в том, что хотя бы одно представимо.) (Можно, конечно, про $k$ и $ab-k$ формулировать, но тогда приходится исключать $k$, кратные $a$ или $b$, и доказательство немного усложняется.)

Положительные коэффициенты немного неудобны тем, что $\mathbb{N}+\mathbb{N}=\{2,3,\dotsc\}\ne\mathbb{N}$, в отличие от $\mathbb{N}_0+\mathbb{N}_0=\mathbb{N}_0$. Поэтому работать немного удобнее с неотрицательными коэффициентами. Хотя дело вкуса.

[Andrey A]

RIP в сообщении #1568728 писал(а):

... работать немного удобнее с неотрицательными коэффициентами. Хотя дело вкуса.

Соглашусь. Тем более, что задача в монетах/купюрах. Рассечёт купюрой одного достоинства — обычное дело. Но считать кол-во непредставимых удобней в положительных, как-то так.
Второе утверждение именно как следствие. Ваше

RIP в сообщении #1568728 писал(а):

... (ровно) одно из чисел $k$, $ab+a+b-k$ имеет вид $ax+by$ с натуральными $x,y$.

, впрочем тоже. Я и писал

Andrey A в сообщении #1568705 писал(а):

Как следствие — ведь $n(a+b)=an+bn$ представимо.

Акцент сделан для итогового $N_{\max}=ab-a-b$ (случай $n=1$). А вот с тремя купюрами пока не понимаю с какой стороны зайти.

[RIP]

Andrey A в сообщении #1568753 писал(а):

Второе утверждение именно как следствие.

Моё второе утверждение не следствие (точнее, следствие наполовину). Из первого утверждения следует только то, что оба числа одновременно представить в нужном виде нельзя. То, что одно из них представить всегда можно, не следует из первого утверждения, а является содержательным самостоятельным утверждением (из которого следует количество непредставимых).

[Andrey A]

Ладно, пусть наполовину ) Выше Вы дали исчерпывающее доказательство, это дорогого стоит. Спасибо. Хотя я тут не ТС.

[Doctor Boom]

RIP в сообщении #1568622 писал(а):

Что касается представимости, то всякое целое число $k$ единственным образом представляется в виде $k=ax+by$ с целыми $x,y$ при условии $0\leqslant x\leqslant b-1$ ($x$ определяется из сравнения $ax\equiv k\pmod{b}$). При этом если $k=ax+by$, то $ab-a-b-k=a(b-1-x)+b(-y-1)$.

Я кстати тогда это показал так, пусть $a>b$, тогда рассмотрим сравнение
$a=s_0 (\mod b)$, т.е. $s_0$ - остаток от деления $a$ на $b$, потом возьмем
$b=s_1 (\mod s_0)$, и т.д. по итерации
$s_{n-2}=s_n (\mod s_{n-1})$
в конце мы придем к $s_{end}=0$. Так вот, если перед этим было $s_{end-1}=1$, то всякое целое число представимо в виде $k=ax+by$, а если было другое натуральное, то не представимо. А $s_{end-1}=1$ может быть только, когда $a$ и $b$ взаимно просты, как-то вот так