Неудачная строка

[Xenia1996]

Для каждой пары натуральных чисел (n, m) рассматриваются n (не обязательно различных) натуральных чисел, выписанных в строку. Строка называется удачной, если между этими числами можно так расставить скобки, знаки сложения и умножения, что значение полученного выражения будет делиться на m, и неудачной в противном случае.

При каком наибольшем n может получиться неудачная строка, если
а) m=2000?
б) m=2010?
в) найти общую формулу для всех m.

[Xenia1996]

Условие задачи понятно? Если нет - спрашивайте. Потому что задача несложная.

[alex1910]

Если n>=m, то любая такая строка удачная (по принципу Дирихле).
Для n=m-1, наверное, несложно придумать неудачную строку, хотя и не уверен.

UPD. Для точной оценки (если m-1 окажется неверным) надо рассматривать разложение m на простые множители - чем больше больших множителей, тем больше максимальное неудачное n.

[Xenia1996]

alex1910 в сообщении #470912 писал(а):

Если n>=m, то любая такая строка удачная (по принципу Дирихле).
Для n=m-1, наверное, несложно придумать неудачную строку, хотя и не уверен.

Найдите неудачную строку для n=100, m=2000

[alex1910]

Xenia1996 в сообщении #470913 писал(а):

alex1910 в сообщении #470912 писал(а):

Если n>=m, то любая такая строка удачная (по принципу Дирихле).
Для n=m-1, наверное, несложно придумать неудачную строку, хотя и не уверен.

Найдите неудачную строку для n=100, m=2000

См. UPD предыдущего сообщения, 2000 имеет максимальный простой множитель 5.

Если m=(P1^A1)*...*(Pk^Ak), то n<=A1P1+A2P2+...+AkPk, то есть 15 + 8 для 2000.

Можно ли в этом неравенстве опуститься ниже верхней границы - это надо думать/считать.

[Xenia1996]

alex1910 в сообщении #470914 писал(а):

Если m=(P1^A1)*...*(Pk^Ak), то n<=A1P1+A2P2+...+AkPk, то есть 15 + 8 для 2000.

Можно ли в этом неравенстве опуститься ниже верхней границы - это надо думать/считать.

Думать/считать - это хорошо. В случае m=2000 попробуйте взять 22 единички и сделать удачную строку.

[alex1910]

Xenia1996 в сообщении #470915 писал(а):

alex1910 в сообщении #470914 писал(а):

Если m=(P1^A1)*...*(Pk^Ak), то n<=A1P1+A2P2+...+AkPk, то есть 15 + 8 для 2000.

Можно ли в этом неравенстве опуститься ниже верхней границы - это надо думать/считать.

Думать/считать - это хорошо. В случае m=2000 попробуйте взять 22 единички и сделать удачную строку.

Зачем? Если она есть - ее можно найти тупым подбором - что неинтересно.
Если ее нет/есть - может быть другая удачная/неудачная строка из 22 чисел - так что задачи это не решит.

В общем, если есть общее идейное и без технических сложностей решение - задача хорошая. Если нет - то плохая.

[Xenia1996]

alex1910 в сообщении #470917 писал(а):

Зачем? Если она есть - ее можно найти тупым подбором - что неинтересно.
Если ее нет/есть - может быть другая удачная/неудачная строка из 22 чисел - так что задачи это не решит.
В общем, если есть общее идейное и без технических сложностей решение - задача хорошая. Если нет - то плохая.

Дело в том, что строка из 22 единичек - неудачная, а любая строка из 23 чисел - удачная. Таким образом, ответ на пункт а) будет 22.
Для общего случая Вы также дали правильный ответ.

[alex1910]

Xenia1996 в сообщении #470919 писал(а):

alex1910 в сообщении #470917 писал(а):

Зачем? Если она есть - ее можно найти тупым подбором - что неинтересно.
Если ее нет/есть - может быть другая удачная/неудачная строка из 22 чисел - так что задачи это не решит.
В общем, если есть общее идейное и без технических сложностей решение - задача хорошая. Если нет - то плохая.

Дело в том, что строка из 22 единичек - неудачная, а любая строка из 23 чисел - удачная. Таким образом, ответ на пункт а) будет 22.
Для общего случая Вы также дали правильный ответ.

Может он и правильный, только там доказано (не написано, но идея явно очевидна после упоминания Дирихле), что если n>= "того что там было написано", то строка заведомо удачная. И ничего не сказано про меньшие n.

Например, 11 = (1+1+1)(1+1+1)+1+1, но доказать/опровергнуть, что любая строка длины 8 удачная - это отдельная работа.

В вашем случае придется доказывать, что 22 единицы - неудачная строка.

[Xenia1996]

alex1910 в сообщении #470922 писал(а):

В вашем случае придется доказывать, что 22 единицы - неудачная строка.

Каюсь, я - дауница
http://e-science.ru/forum/index.php?showtopic=32846

[alex1910]

Xenia1996 в сообщении #470980 писал(а):

alex1910 в сообщении #470922 писал(а):

В вашем случае придется доказывать, что 22 единицы - неудачная строка.

Каюсь, я - дауница
http://e-science.ru/forum/index.php?showtopic=32846

Нет уж, нет уж. Запостили задачу - предъявите ответ. Чтобы не сильно напрягаться, пусть m=11 - уже это будет непросто.