vlad
Гений-Говорун
Offline
Сообщений: 1005
СПАСИБО
-вы поблагодарили: 735
-вас поблагодарили: 327
|
|
� : Октябрь 02, 2014, 10:20:20 � |
|
Человек задумал N натуральных чисел m 1,m 2,...,m n. Ваша задача - отгадать их. Вы можете задавать ему вопросы, содержащие числа a 1,a 2,...,a n, на что он будет вам сообщать сумму a 1*m 1 + a 2*m 2 + ... + a n*m n. Какое минимальное число вопросов необходимо задать, чтобы отгадать все числа m 1,m 2,...,m n? В это трудно поверить, но ответ 1 вопрос Если числа a i - произвольные, то задав 1 вопрос, выбрав в качестве a 1, a 2, ..., a n несоизмеримые числа, натуральные коэффициенты m i в их линейной комбинации определятся однозначно. Помогите владу в это поверить это проверить. Допустим загаданные числа 3,14,15,9,2,6,5 Набор просых 13,19,31,47,71,101,137 вроде подходит имеем 3*13+14*19+15*31+9*47+2*71+6*101+5*137=2626 ЧТО ДАЛЬШЕ
|
|
|
Записан
|
SATYAT NASTI PARO DHARMAH
|
|
|
BIVES
Умник
Offline
Сообщений: 687
СПАСИБО
-вы поблагодарили: 53
-вас поблагодарили: 272
|
|
� Ответ #1 : Октябрь 03, 2014, 09:03:57 � |
|
Давайте упростим. Пусть a1=3, a2=14. Если взять m1=13, m2=19, то уравнение 13x+19y=305 имеет решение в целых числах: x=19r+22, y=1-13r, где r - любое целое. Очевидно, что для того чтобы x и y были натуральные r должно быть равным -1. Т. е. натуральное решение одно x=3, y=14. Легко показать, что если m1 и m2 - разные простые числа, такие, что m1>a1, m2>a2, то уравнение m1x+m2y=m1a1+m2a2 имеет одно решение в натуральных числах x=a1, y=a2.
Если взять a1=3, a2=14, a3=2, m1=13, m2=19, m3=5, то уравнение 13x+19y+5z=315 будет иметь кроме x=3, y=14, z=2, еще, например, x=3, y=9, z=21. Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).
|
|
|
|
vlad
Гений-Говорун
Offline
Сообщений: 1005
СПАСИБО
-вы поблагодарили: 735
-вас поблагодарили: 327
|
|
� Ответ #2 : Октябрь 03, 2014, 09:29:51 � |
|
Давайте упростим. Пусть a1=3, a2=14. Если взять m1=13, m2=19, то уравнение 13x+19y=305 имеет решение в целых числах: x=19r+22, y=1-13r, где r - любое целое. Очевидно, что для того чтобы x и y были натуральные r должно быть равным -1. Т. е. натуральное решение одно x=3, y=14. Легко показать, что если m1 и m2 - разные простые числа, такие, что m1>a1, m2>a2, то уравнение m1x+m2y=m1a1+m2a2 имеет одно решение в натуральных числах x=a1, y=a2.
за это спасибки. пример хороший. хоть что-то уже прояснилось. Если взять a1=3, a2=14, a3=2, m1=13, m2=19, m3=5, то уравнение 13x+19y+5z=315 будет иметь кроме x=3, y=14, z=2, еще, например, x=3, y=9, z=21.
набор m 1=13, m 2=19, m 3=5 брать нельзя из-за m 3=5: пары 5,13 и 5,19 не есть несоизмеримыми( другими словами и 13/5, и 19/5 не иррациональны) Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).
дополнительное условие - это дельная мысль, но думаю оно должно иметь немножечко другой вид. потому, что, допустим, для a 1=3, a 2=14, a 3=2, m 1=13, m 2=19, m 3= 5101 имеем 13>14.
|
|
|
Записан
|
SATYAT NASTI PARO DHARMAH
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486
|
|
� Ответ #3 : Октябрь 03, 2014, 15:40:13 � |
|
Давайте упростим. Пусть a1=3, a2=14. Если взять m1=13, m2=19, то уравнение 13x+19y=305 имеет решение в целых числах: x=19r+22, y=1-13r, где r - любое целое. Очевидно, что для того чтобы x и y были натуральные r должно быть равным -1. Т. е. натуральное решение одно x=3, y=14. Легко показать, что если m1 и m2 - разные простые числа, такие, что m1>a1, m2>a2, то уравнение m1x+m2y=m1a1+m2a2 имеет одно решение в натуральных числах x=a1, y=a2.
Если взять a1=3, a2=14, a3=2, m1=13, m2=19, m3=5, то уравнение 13x+19y+5z=315 будет иметь кроме x=3, y=14, z=2, еще, например, x=3, y=9, z=21. Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).
А если взять 13x+19y=5180, то тут уже получится куча решений (150,170); (169,157);(182,144) и т.д. Так что для любого набора натуральных a_1,a_2,..a_n найдется достаточно большая их линейная комбинация с большим количеством решений
|
|
|
Записан
|
|
|
|
BIVES
Умник
Offline
Сообщений: 687
СПАСИБО
-вы поблагодарили: 53
-вас поблагодарили: 272
|
|
� Ответ #4 : Октябрь 03, 2014, 16:36:41 � |
|
Давайте упростим. Пусть a1=3, a2=14. Если взять m1=13, m2=19, то уравнение 13x+19y=305 имеет решение в целых числах: x=19r+22, y=1-13r, где r - любое целое. Очевидно, что для того чтобы x и y были натуральные r должно быть равным -1. Т. е. натуральное решение одно x=3, y=14. Легко показать, что если m1 и m2 - разные простые числа, такие, что m1>a1, m2>a2, то уравнение m1x+m2y=m1a1+m2a2 имеет одно решение в натуральных числах x=a1, y=a2.
Если взять a1=3, a2=14, a3=2, m1=13, m2=19, m3=5, то уравнение 13x+19y+5z=315 будет иметь кроме x=3, y=14, z=2, еще, например, x=3, y=9, z=21. Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).
А если взять 13x+19y=5180, то тут уже получится куча решений (150,170); (169,157);(182,144) и т.д. Так что для любого набора натуральных a_1,a_2,..a_n найдется достаточно большая их линейная комбинация с большим количеством решений zhekas, я исходил из того, что мы знаем max(a_1, a_2) и берем в качестве m_1 и m_2 простые числа большие чем max(a_1, a_2), тогда уравнение x*m_1+y*m_2=a_1*m_1+ a_2*m_2 имеет в натуральных числах только одно решение. Ясно, что задав 1 вопрос, назвав при этом простые числа не удастся назвать все загаданные числа. Я воспринимал вопрос, заданный vlad как альтернативу предложенному вами решению.
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486
|
|
� Ответ #5 : Октябрь 03, 2014, 21:10:51 � |
|
Давайте упростим. Пусть a1=3, a2=14. Если взять m1=13, m2=19, то уравнение 13x+19y=305 имеет решение в целых числах: x=19r+22, y=1-13r, где r - любое целое. Очевидно, что для того чтобы x и y были натуральные r должно быть равным -1. Т. е. натуральное решение одно x=3, y=14. Легко показать, что если m1 и m2 - разные простые числа, такие, что m1>a1, m2>a2, то уравнение m1x+m2y=m1a1+m2a2 имеет одно решение в натуральных числах x=a1, y=a2.
Если взять a1=3, a2=14, a3=2, m1=13, m2=19, m3=5, то уравнение 13x+19y+5z=315 будет иметь кроме x=3, y=14, z=2, еще, например, x=3, y=9, z=21. Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).
А если взять 13x+19y=5180, то тут уже получится куча решений (150,170); (169,157);(182,144) и т.д. Так что для любого набора натуральных a_1,a_2,..a_n найдется достаточно большая их линейная комбинация с большим количеством решений zhekas, я исходил из того, что мы знаем max(a_1, a_2) и берем в качестве m_1 и m_2 простые числа большие чем max(a_1, a_2), тогда уравнение x*m_1+y*m_2=a_1*m_1+ a_2*m_2 имеет в натуральных числах только одно решение. Ясно, что задав 1 вопрос, назвав при этом простые числа не удастся назвать все загаданные числа. Я воспринимал вопрос, заданный vlad как альтернативу предложенному вами решению. Изначально, я так понимаю, тема создавалась, чтобы уменьшить кол-во вопросов с двух до одного. zhekas, я исходил из того, что мы знаем max(a_1, a_2) и берем в качестве m_1 и m_2 простые числа большие чем max(a_1, a_2), тогда уравнение
Если мы знаем max(a_1, a_2), то тогда смысл и у моего решения в первом вопросе отпадает.
|
|
|
Записан
|
|
|
|
|