задача Мензы

[shwedka]

Сейчас я на конференции в одном симпатичном германском городе.
Обсуждая с местными аспирантами разную математику,
Услышала я от них такую задачу.
Они ее назвали задачей мензы. Менза, на студенческом немецком, означает студенческую столовую.
Там платить за обед надо.
Вопрос, можно ли всегда оплатить обед монетками в 1,2,5евро центов,
используя простое количество или ноль монет каждого вида???

[Sonic86]

shwedka в сообщении #923304 писал(а):

поздно ли

Видимо, надо читать "можно ли".

shwedka в сообщении #923304 писал(а):

поздно ли всегда оплатить обед монетками в 1,2,5евро центов,
используя простое количество или ноль монет каждого вида???

Усложненный Гольдбах?

(Оффтоп)

А потом написать слова Ландау: "простые числа ведь нужны для того, чтобы их умножать, а не складывать"

[ex-math]

Если обед стоит нечетное число евроцентов, то пусть сначала бинарную проблему решат. А если четное, то любой достаточно дорогой обед можно оплатить.

[Nilenbert]

Ну а если обед стоит 1 евроцент?

[ex-math]

Как Вы понимаете, интересны обеды растущей стоимости. Возможность оплатить обед любой фиксированной цены можно, хотя бы теоретически, проверить перебором. Потому-то тернарная проблема была решена Виноградовым, а не теми, кто спустя 60 лет довел этот конечный перебор до конца.

[Red_Herring]

ex-math в сообщении #923350 писал(а):

Потому-то тернарная проблема была решена Виноградовым, а не теми, кто спустя 60 лет довел этот конечный перебор до конца.

Я бы все же был более осторожным с подобными утверждениями. Для того чтобы завершить доказательство требовалось опустить планку очень существенно и лишь потом осуществить перебор. Безусловно И.М.Виноградов сделал очень важный (м.б. решающий—как неспециалисту мне трудно судить) шаг, но решил ее Харальд Хельфготт.

ПС. В какой-то момент всем известный "Доктор Яо" утверждал, что гипотезу Пуанкаре в основном доказал Р.Гамильтон

[ex-math]

Red_Herring
Виноградов не просто сделал решающий шаг, а именно решил проблему.
Я не говорю, что оставшийся перебор был тривиально выполним, там действительно была большая работа по "снижению планки", но это, при всем уважении, лишь отделочные работы, а не решение проблемы. Это все имхо, но как (бывшего) специалиста в этой области.

[Red_Herring]

ex-math
Если я правильно понимаю, после работ И.М.Виноградова проблема решена не была. И учитывая, что между этими работами и окончательным решением прошло несколько десятилетий в те времена теория чисел еще не дозрела до решения. Но дело даже не в этом: здесь дело не в приоритете, а в том, что считать решением.

[alexo2]

shwedka в сообщении #923304 писал(а):

Вопрос, можно ли всегда оплатить обед монетками в 1,2,5евро центов,
используя простое количество или ноль монет каждого вида???

Более того, похоже, что если обед больше 7-ми центов, то его можно оплатить обязательно используя монеты всех достоинств - проверил перебором до 5-ти евро (обед, вроде, больше не должен стоить в студенческой столовой? )
Интересно, что для чисел кратных трем и простых в разы меньше вариантов чем для остальных (начиная со второй сотни - вариантов оплаты "для остальных" уже десятки, в то время как для простых и кратных трем - единицы)..
Хотя общая тенденция вроде бы - увеличение количества вариантов с увеличением стоимости обеда.

[ex-math]

Red_Herring
Строго говоря, это две разные проблемы, одна для достаточно больших $N$, другая для $N\geqslant9$. Вторая оставалась недорешенной после Виноградова, но и большого интереса к ней уже не было, в отличие от бинарной. Может, это просто традиция нашей научной школы, но у нас всегда считали подобную проблему в принципе решенной, если она была решена для достаточно больших $N$. Честно говоря, удивлен, что существует другой взгляд на это. Я не хочу умалять заслуг Хельфготта, но это результат совсем другого уровня.

[Red_Herring]

ex-math
Я отнюдь не пытаюсь обсуждать уровень результатов или интереса к проблеме. Но и английская и русская Википедии воздавая почести И.М.В. все же утверждают что окончательно доказал гипотезу Харальд Хельфготт (т.ч. удивляться не стоит).

Кроме того, существует масса задач, в которых "для всех $N$" и "для всех достаточно больших $N$" сильно не равнозначны. Например в задаче о собственных значениях Лапласиана за большие собственные значения и за наименьшие ответственны совершенно различные геометрические характеристики области. Или в задаче о числе целых точек в шаре именно двумерный случай остается (или по крайней мере оставался несколько лет назад) не вполне решенным: точная оценка остатка неизвестна (опять таки И.М.В. решил задачу в размерностях $\ge 3$).

[ex-math]

А разве в случае трехмерного шара точный порядок остатка известен?

[patzer2097]

Red_Herring в сообщении #923574 писал(а):

Кроме того, существует масса задач, в которых "для всех $N$" и "для всех достаточно больших $N$" сильно не равнозначны.

мне кажется, что ключевое различие между этими примерами (задачей о числе целых точек и проблемой Гольдбаха) состоит в том, что результат И.М.Виноградова сводит решение второй из них к конечному вычислению, а сходство про "достаточно большие $n$" здесь может быть только внешним

[g______d]

patzer2097 в сообщении #923679 писал(а):

результат И.М.Виноградова сводит решение второй из них к конечному вычислению

Говорят, что задача вычисления гомотопических групп сфер тоже сводится к конечным вычислениям, но сам результат о сводимости безумной радости не произвел, когда был получен.

В какой-то из книжек Вавилова было классное наблюдение о том, что результаты о чем-то бесконечном обычно проще, чем результаты о чем-то очень большом, но конечном.

[Red_Herring]

ex-math в сообщении #923654 писал(а):

А разве в случае трехмерного шара точный порядок остатка известен?

Кажется, мое воспоминание о семинаре многолетней давности не вполне точно.

(Оффтоп)

Я потенциальный благодетель человечества ибо я знаю, как сделать всех людей счастливыми (кроме быть может конечного числа)