Математический форум Math Help Planet
http://mathhelpplanet.com/

Восстановить числа по их попарным суммам
http://mathhelpplanet.com/viewtopic.php?f=50&t=64069
Страница 1 из 4

Автор:  irafat [ 23 фев 2019, 23:55 ]
Заголовок сообщения:  Восстановить числа по их попарным суммам

Двое играют в такую игру. Первый загадывает 8 действительных чисел (не обязательно различных) и пишет на листочке все их попарные суммы в произвольном порядке (некоторые из них могут совпадать). Второй по полученным 28 суммам должен определить исходные числа. Всегда ли он может гарантированно это сделать?

То есть, заданы 28 чисел, про которые известно только, что они являются попарными суммами 8 чисел. Можно ли восстановить эти 8 чисел?

Автор:  swan [ 24 фев 2019, 00:24 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Если семь нулей, восьмое никак не восстановить

Автор:  irafat [ 24 фев 2019, 14:00 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Можно составить систему уравнений, произвольно приписывая им в качестве правой части эти 28 чисел (а1, а2,.., а28).

х1+х2=а1
х1+х3=а2
................
х27+х28=а28

И решить эту систему можно (или нельзя?) - получим в качестве решений 8 чисел (однозначно?).

Вопрос в том, что если произвольно переставлять правые части в системе уравнений, то мы будем получать в качестве решений те же самые числа (пусть в другом порядке).

Автор:  swan [ 24 фев 2019, 14:01 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Вчера когда читал - подумал про попарные произведения...
Мой комментарий не в тему

Автор:  Li6-D [ 24 фев 2019, 15:10 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Предлагаю упорядочить суммы по убыванию или возрастанию.
По трем наибольшим суммам [math]a1 \geqslant a2 \geqslant a3[/math] всегда можно найти три самых больших исходных числа.
Аналогично с тремя наименьшими суммами.
Попарно суммируя найденные числа будем выкидывать 15 получивших сумм из исходного списка.
Из 13-ти оставшихся можно рассмотреть самое большое и самое маленькое число...

PS Мда, тут в начале есть изъян - на третьем месте может оказаться сумма x1+x4, а не x2+x3...

Автор:  irafat [ 24 фев 2019, 18:35 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Кстати, для двух чисел определить невозможно - всего одно уравнение (суммы самих с собой не рассматриваются)
х1+х2=а

Для трех чисел а1 а2 а3 уже можно

х1+х2=а1
х1+х3=а2
х2+х3=а3

х1=(а1+а2-а3)/2
х3=а2-х1=(а2+а3-а1)/2
х2=а3-х3=(а3+а1-а2)/2

То есть, в решении берутся суммы двух чисел минус третье число
И от порядка чисел этот алгоритм решения не зависит
Так что, для трех чисел решение не зависит от порядка задания чисел - эти три числа определяются однозначно, с точностью до порядка следования.

Вопрос про возможное обобщение на произвольное N число заданных чисел.

Автор:  Galina Alexandrovna [ 05 мар 2019, 11:21 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

irafat.
Задайте 28 чисел, которые являются попарными суммами 8 чисел. А я попробую восстановить эти числа. Если получится можно будет обсуждать, как это можно сделать.

Автор:  Galina Alexandrovna [ 08 мар 2019, 10:34 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Я нашла вариант решения предложенной задачи. Я технолог, а технологи все проверяют экспериментально. Для чистоты эксперимента попарные суммы чисел должен посчитать кто-то другой. Но приходится считать самой. Задаем следующие числа: х1 =18, х2 = 36, х3 = 44, х4 = 52, х5 = 68, х6 = 73, х7 = 84, х8 = 92.
Получаем попарные суммы.
х1+х2 = 18+36 = 54
х1+х3 = 18+44 = 62
х1+х4 = 18+52 = 70
х1+х5 = 18+68 = 86
..................................
х5+х8 = 68+92 = 160
х6+х7 = 73+84 = 157
х6+х8 = 73+92 = 165
х7+х8 = 84+92 = 176,
Полученные попарные суммы располагаем в порядке возрастания.
54, 62, 70, 80, 86, 88, 91, 96, 102, 104, 109, 110, 112, 117, 120, 120, 125, 127, 128, 136, 136, 141, 144, 152, 157, 160, 165,176.
Находим первые 3 числа.
х1+х2 = 54 однозначно
х1+х3 = 62 однозначно
х2+х3 = 70 ?
Решение показывает, что полученные х1, х2, х3 не удовлетворяют условиям.
Если х2 + х3 не равно 70, то х2 +х3 = 80, 80 входит в четверку самых маленьких сумм.
х1+х2 = 54
х1+х3 = 62
х2+х3 = 80
2х1+2х2+2х3 = 196, х1+х2+х3 = 98, отсюда х1 = 18, х2 = 36, х3 = 44.
х4 = 70-18 = 52. 70 входит в число четырех самых маленьких попарных сумм.
Рассмотрим 4 самые большие попарные суммы.
х8+х7 = 176 однозначно
х8+х6 = 165 однозначно
х7+х6 = 160?
Полученные х8,х7,х6 не подходят к условию задачи. Тогда
х7+х8 = 176
х6+х8 = 165
х6+х7 = 157
2х6 + 2х7 + 2х8 =498, х6+х7+х8 = 249.
х6 = 73, х7 = 84, х8 = 92, х5 = 160 - х8 = 160 -92 = 68 . Число 160 входит в четверку самых больших попарных сумм.

Автор:  Li6-D [ 09 мар 2019, 10:57 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Предложу упорядоченный набор из 28 чисел для обкатки алгоритмов решения задачи:
7.408, 9.075, 9.789, 11.033, 12.091, 15.425, 16.139,
17.383, 17.806, 18.441, 19.05, 19.764, 19.764, 20.108,
20.822, 22.066, 26.114, 26.961, 27.781, 28.495, 29.739,
30.797, 33.311, 34.978, 35.692, 36.936, 37.994, 45.667.
Это точные числа, полученные попарным сложением восьми чисел, которые нужно определить.
Такие наборы легко получить пользуясь кодом под катом:
▼ Код. Внимание - раскрыты исходные числа!
M=(0.529,6.879,8.546,9.260,10.504,11.562,19.235,26.432);
w=width M-1;
M2=0;
for(z1,0,w,for(z2,z1+1,w,M2=(M2,M[z1]+M[z2]));
print "Попарные суммы до упорядочивания:";
print M2=M2[1,width M2-1];
print "Попарные суммы после упорядочивания:";
print sort M2;

Получается:
Изображение

Автор:  Li6-D [ 11 мар 2019, 00:21 ]
Заголовок сообщения:  Re: Восстановить числа по их попарным суммам

Алгоритм дешифровки по попарным суммам:
/*Заданная матрица-строка из попарных сумм*/
M2=(348,-166,-13,-5,20,24,31,35,38,43,46,49,53,1,10,16,54,55,355,-269,60,
70,-483,-468,-460,337,78,503,-454,-435,-424,-417,114,121,312,209,
79,84,86,97,103,372,186,-400,201,269,61,67,289,304,215,234,245,252,318);
/*Восстановление исходных чисел по их попарным суммам*/
M2=sort M2;
n=(sqrt(8*width M2+1)+1)/2;
if(n==2 or frac n,goto ERR0,0);
Md=(M2[0]+M2[1],M2[0]-M2[1],-M2[0]+M2[1])/2;
if(n==3,return M=M2[2]/2*(-1,1,1)+Md,0);
M2=M2[2,width M2-1];
f=0;
LB0:
M=M2[f]/2*(-1,1,1)+Md;
Mx=if(f,(M2[0,f-1],M2[f+1,width M2-1]),M2[1,width M2-1]);
LB1:
a=M[0];
k=width M-1;
d=Mx[0]-a;
j=0;
LB2:
if(j++<=k,s=M[j]+d,goto LB3);
w=width Mx-1;
i=0;
if(i++<=w,0,if(f++>n-2,goto ERR1,goto LB0));
if(s==Mx[i],0,gotor-1);
Mx=if(i==w,Mx[0,w-1],(Mx[0,i-1],Mx[i+1,w]));
goto LB2;
LB3:
M=(M,d);
if(w-1,Mx=Mx[1,w-1],return M);
goto LB1;
ERR0:
print "Ошибка: в матрице должно быть 3,6,10,21,28... чисел";
return;
ERR1:
print "Ошибка: числа в матрице не являются попарными суммами нескольких чисел";

Проще оказалось написать программку, чем описать методику расчета.
Кому интересно могу объяснить нюансы.
Наверняка существуют проще способы решения, раз задача с олимпиады.
Возможно есть простые примеры, когда для двух разных наборов из восьми чисел получатся один набор попарных сумм этих чисел.
Тогда ответ - "Нет, не всегда".
Изображение

Страница 1 из 4 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/