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

[Doctor Boom]

Пусть надо разложить число $X$, находим такое $n$, что $3n<X<5n$, пусть в начале все тройки, если последовательно заменять тройки на пятерки, будем идти с шагом два. Чтобы сместиться на единицу (и идти с там же шагом), прибавляем (или отнимаем) трехдолларовую купюру, как итог достигнем $X$

[Mihr]

Gepidium в сообщении #1568396 писал(а):

Почему выгодней представить остаток как $t=-1$, чем как $t=2$?

$-1$ не может называться остатком. По определению остаток - это неотрицательное целое число, меньшее делителя. Нам удобнее перейти от $2$ к $-1$, чтобы механически получить три минимальные подходящие суммы: $8, 9, 10$ долларов.

(Оффтоп)

Gepidium в сообщении #1568396 писал(а):

А почему у Вас на профиле никнейм без цвета? Вы же ЗУ!

Любой ЗУ может выбрать синий цвет никнейма либо чёрный - как у всех. Вы наверняка видели, что ники многи ЗУ (не только мой) не выделены синим.

[gris]

Теперь надо для каждого $N$ найти число способов формулой. А для начала для первых $N$ посчитать программкой (ТС же сделала это ) и запихать результат в OEIS, если его там нет.

[Gagarin1968]

После того как я прочитал условие задачи, в голове вспыхнула какая-то лампочка. Как будто я уже видел где-то что-то подобное. И сегодня утром вспомнил.
Прошу приветствовать! Популярные лекции по математике, вып.3, Соминский "Метод математической индукции", Москва, 1973 г., стр. 24, задача 10.



Как говорится, всё уже украдено до нас! Gepidium, откуда Вы взяли Вашу задачу?
Интересно, это воровство, плагиат, или переделка старого? Вот оно, тлетворное влияние Запада! Южноокеанские доллары на острове - смешно, право слово!

[svv]

Мне кажется, решение Mihr станет ещё нагляднее, если ему придать такой вид. Запишем натуральные числа в виде таблички:
$\begin{matrix}0&3&6&9&12&...\\1&4&7&10&13&...\\2&5&8&11&14&...\end{matrix}$
Справа от любого числа $n$ стоит число $n+3$. И если $n$ представимо суммой троек и пятёрок, то число справа (а значит, и все числа справа) тоже.
Будем «представимость» отмечать цветом. Поскольку $0$, $5$ и $10$ представимы, получаем следующее:
$\begin{matrix}{\color{magenta}0}&{\color{magenta}3}&{\color{magenta}6}&{\color{magenta}9}&{\color{magenta}12}&{\color{magenta}...} \\1&4&7&{\color{magenta}10}&{\color{magenta}13}&{\color{magenta}...} \\2&{\color{magenta}5}&{\color{magenta}8}&{\color{magenta}11}&{\color{magenta}14}&{\color{magenta}...}\end{matrix}$

[Gepidium]

Gagarin1968 в сообщении #1568422 писал(а):

Gepidium, откуда Вы взяли Вашу задачу?

Из "Methodical manual and collection of problems on number theory", издано в 2013 году, Иерусалимский универ. Я там учусь.
Да, задача точь в точь как русская. Наверно кто-то содрал.

[Doctor Boom]

Осталось обобщить задачу о расплате купюрами $n_1$ и $n_2$ товара стоимостью $X>K$

[Mihr]

(Gepidium)

Gepidium в сообщении #1568437 писал(а):

Из "Methodical manual and collection of problems on number theory", издано в 2013 году, Иерусалимский универ. Я там учусь.

Gepidium в сообщении #1559458 писал(а):

Я познакомилась с Мариной в 2005 в Болгарии, городе Благоевграде на студенческой олимпиаде.

Заинтриговали

[Gepidium]

(Оффтоп)

Mihr в сообщении #1568495 писал(а):

Заинтриговали

Все правильно. Тогда я заканчивала школу. Поступила в универ, но отучилась только год, а потом переехала с родителями в другую страну. И в 31 год решила закончить образование, правда экономическое. А тут еще коронавирус отнял полтора года...

[Mihr]

(Gepidium)

Gepidium, ну, что ж, учиться можно (и нужно) всю жизнь. Успехов!

[Gepidium]

(Mihr)

Mihr в сообщении #1568510 писал(а):

Успехов!

Спасибо за добрые слова и за помощь.

[Andrey A]

Doctor Boom в сообщении #1568480 писал(а):

Осталось обобщить задачу о расплате купюрами $n_1$ и $n_2$ товара стоимостью $X$

Возьмем частный случай $n_1 \neq n_2$ — некоторая пара простых. Где-то на страницах dxdy. доказано, что из произвольных вз. простых $a+b=n_1n_2$ формой $n_1 \cdot x+n_2 \cdot y$ представимо строго либо $a$, либо $b$ (сумма арифметическая). Всего таких пар $\varphi (n_1,n_2) /2$, где $\varphi ()$ — функция Эйлера. Поэтому непредставимых ровно $(n_1-1)(n_2-1)/2$. Наибольшее из них, если не ошибаюсь, $n_1n_2-n_1-n_2.$

Исправлено.

[Andrey A]

Похоже, формулы $(n_1-1)(n_2-1)/2$ (количество непредставимых) и $n_1n_2-n_1-n_2$ (наибольшее из непредставимых) верны и для произвольной пары взаимно простых $n_1,n_2.$ Просто потому, что свойства простых глубоко не затрагивались, и можно взять к примеру $n_1=8,n_2=9$ "квазипростыми" относительно предыдущих рассуждений. Здесь получаем $28$ непредставимых, включая наибольшее $X=55$, и $X>55$ без сдачи. Хорошо бы проверить.

[Andrey A]

Upd

Если в предыдущем нет ошибки и количество непредставимых не очень интересует, можно взять аргументом наибольшее из непредставимых. Обозначим его $N_{\max}.$ В стартовом условии было $N_{\max}=7$, и в любом случае это нечетное число, поскольку $N_{\max}+1=n_1n_2-n_1-n_2+1=(n_1-1)(n_2-1)$ есть удвоенное количество непредставимых, т.е. четное. Ну, и прибавляя единицу к элементам всех возможных пар множителей числа $N_{\max}+1$, получаем все возможные пары купюр, если они взаимно просты. Так даже интересней.
Для $N_{\max}=17$, к примеру, получаем $17+1=18=1 \cdot18=2 \cdot 9=3 \cdot 6,$ откуда $(d_1;d_2)=(2;19),(3;10),(4;7).$ Все пары вз. просты, идут в зачет.

Иметь не вз. простые купюры $d_1,d_2$ не очень практично: цены в магазине должны быть кратны $\gcd (d_1,d_2)$. А поделив на это сумму и слагаемые, имеем ту же задачу )

[gris]

Andrey A, только хотел пошутить, что купюры сейчас только бонистов интересуют, как вспомнил Столовую N1 И благостно наспех накидал программку проверки. Она ещё количество способов считает :

{N=vector(400);
for (n=2, 7, for (m=2,n-1, 
 if(gcd(n,m)==1,nm=n*m;for (l=1,nm+1,N[l]=0;);
  for (i=0,nm,for (j=0,floor(n-i*n/m), 
   k=i*n+j*m+1; if (k<nm+2,N[k]++);
  ));
   numf=0; last=0; for (l=2,nm+1, if (N[l]==0,numf++;last=l-1));
   print (n," ",m," total ",numf,"  ( (n_1-1)(n_2-1)/2=",(n-1)*(m-1)/2,")   max ", last,"   ( n_1n_2-n_1-n_2=",nm-n-m,")" ); 
 );
))}
3 2 total 1   ( (n_1-1)(n_2-1)/2=1)    max 1   ( n_1n_2-n_1-n_2=1)
4 3 total 3   ( (n_1-1)(n_2-1)/2=3)    max 5   ( n_1n_2-n_1-n_2=5)
5 2 total 2   ( (n_1-1)(n_2-1)/2=2)    max 3   ( n_1n_2-n_1-n_2=3)
5 3 total 4   ( (n_1-1)(n_2-1)/2=4)    max 7   ( n_1n_2-n_1-n_2=7)
5 4 total 6   ( (n_1-1)(n_2-1)/2=6)    max 11   ( n_1n_2-n_1-n_2=11)
6 5 total 10  ( (n_1-1)(n_2-1)/2=10)   max 19   ( n_1n_2-n_1-n_2=19)
7 2 total 3   ( (n_1-1)(n_2-1)/2=3)    max 5   ( n_1n_2-n_1-n_2=5)
7 3 total 6   ( (n_1-1)(n_2-1)/2=6)    max 11   ( n_1n_2-n_1-n_2=11)
7 4 total 9   ( (n_1-1)(n_2-1)/2=9)    max 17   ( n_1n_2-n_1-n_2=17)
7 5 total 12  ( (n_1-1)(n_2-1)/2=12)   max 23   ( n_1n_2-n_1-n_2=23)
7 6 total 15  ( (n_1-1)(n_2-1)/2=15)   max 29   ( n_1n_2-n_1-n_2=29)

9 8 total 28  ( (n_1-1)(n_2-1)/2=28)   max 55   ( n_1n_2-n_1-n_2=55)

На небольших банкнотах подтверждается!
Надеюсь, ТС простит небольшой оффтопик