Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: vlad от Октябрь 02, 2014, 10:20:20



Название: как пользоваться несоизмеримостью 2-х чисел
Отправлено: vlad от Октябрь 02, 2014, 10:20:20
Человек задумал N натуральных чисел m1,m2,...,mn. Ваша задача - отгадать их. Вы можете задавать ему вопросы, содержащие числа a1,a2,...,an, на что он будет вам сообщать сумму a1*m1 + a2*m2 + ... + an*mn. Какое минимальное число вопросов необходимо задать, чтобы отгадать все числа m1,m2,...,mn?

В это трудно поверить, но ответ 1 вопрос   :think: :o  :roll:
Если числа ai - произвольные, то задав 1 вопрос, выбрав в качестве a1, a2, ..., an несоизмеримые числа, натуральные коэффициенты mi в их линейной комбинации определятся однозначно.

Помогите владу в это поверить это проверить.
Допустим загаданные числа 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
ЧТО ДАЛЬШЕ  ??? :help: :wall: :girlcry:


Название: Re: как пользоваться несоизмеримостью 2-х чисел
Отправлено: BIVES от Октябрь 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).


Название: Re: как пользоваться несоизмеримостью 2-х чисел
Отправлено: vlad от Октябрь 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.


набор m1=13, m2=19, m3=5 брать нельзя из-за m3=5: пары 5,13 и 5,19 не есть несоизмеримыми( другими словами и 13/5, и 19/5 не иррациональны)

Цитировать

Поэтому, какие дополнительные условия накладывать на m1, m2, m3 не понятно. Для случая трех неизвестных по видимому условие выглядит так: min(m1, m2, m3)>max( a1, a2, a3).


дополнительное условие - это дельная мысль, но думаю оно должно иметь немножечко другой вид. потому, что, допустим, для a1=3, a2=14, a3=2, m1=13, m2=19, m3=5101 имеем 13>14.



Название: Re: как пользоваться несоизмеримостью 2-х чисел
Отправлено: zhekas от Октябрь 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 найдется достаточно большая их линейная комбинация с большим количеством решений


Название: Re: как пользоваться несоизмеримостью 2-х чисел
Отправлено: BIVES от Октябрь 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 как альтернативу предложенному вами решению.


Название: Re: как пользоваться несоизмеримостью 2-х чисел
Отправлено: zhekas от Октябрь 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), то тогда смысл и у моего решения в первом вопросе отпадает.