2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Неудачная строка
Сообщение24.07.2011, 14:44 


01/10/10

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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 15:55 


01/10/10

2116
Израиль (племянница БизиБивера)
Условие задачи понятно? Если нет - спрашивайте. Потому что задача несложная.

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 16:47 


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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 16:53 


01/10/10

2116
Израиль (племянница БизиБивера)
alex1910 в сообщении #470912 писал(а):
Если n>=m, то любая такая строка удачная (по принципу Дирихле).
Для n=m-1, наверное, несложно придумать неудачную строку, хотя и не уверен.

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 16:55 


21/07/10
555
Xenia1996 в сообщении #470913 писал(а):
alex1910 в сообщении #470912 писал(а):
Если n>=m, то любая такая строка удачная (по принципу Дирихле).
Для n=m-1, наверное, несложно придумать неудачную строку, хотя и не уверен.

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


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

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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 17:05 


01/10/10

2116
Израиль (племянница БизиБивера)
alex1910 в сообщении #470914 писал(а):

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

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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 17:12 


21/07/10
555
Xenia1996 в сообщении #470915 писал(а):
alex1910 в сообщении #470914 писал(а):

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

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

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


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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 17:20 


01/10/10

2116
Израиль (племянница БизиБивера)
alex1910 в сообщении #470917 писал(а):
Зачем? Если она есть - ее можно найти тупым подбором - что неинтересно.
Если ее нет/есть - может быть другая удачная/неудачная строка из 22 чисел - так что задачи это не решит.
В общем, если есть общее идейное и без технических сложностей решение - задача хорошая. Если нет - то плохая.

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 17:30 


21/07/10
555
Xenia1996 в сообщении #470919 писал(а):
alex1910 в сообщении #470917 писал(а):
Зачем? Если она есть - ее можно найти тупым подбором - что неинтересно.
Если ее нет/есть - может быть другая удачная/неудачная строка из 22 чисел - так что задачи это не решит.
В общем, если есть общее идейное и без технических сложностей решение - задача хорошая. Если нет - то плохая.

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


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

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

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 22:56 


01/10/10

2116
Израиль (племянница БизиБивера)
alex1910 в сообщении #470922 писал(а):
В вашем случае придется доказывать, что 22 единицы - неудачная строка.

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

 Профиль  
                  
 
 Re: Неудачная строка
Сообщение24.07.2011, 23:43 


21/07/10
555
Xenia1996 в сообщении #470980 писал(а):
alex1910 в сообщении #470922 писал(а):
В вашем случае придется доказывать, что 22 единицы - неудачная строка.

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: nnosipov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group