Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Восстановить числа по их попарным суммам
СообщениеДобавлено: 23 фев 2019, 23:55 
Не в сети
Продвинутый
Зарегистрирован:
22 дек 2018, 17:13
Сообщений: 74
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 00:24 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4328
Cпасибо сказано: 71
Спасибо получено:
926 раз в 844 сообщениях
Очков репутации: 211

Добавить очки репутацииУменьшить очки репутации
Если семь нулей, восьмое никак не восстановить

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 14:00 
Не в сети
Продвинутый
Зарегистрирован:
22 дек 2018, 17:13
Сообщений: 74
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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

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

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


Последний раз редактировалось irafat 24 фев 2019, 14:09, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 14:01 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4328
Cпасибо сказано: 71
Спасибо получено:
926 раз в 844 сообщениях
Очков репутации: 211

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 15:10 
Не в сети
Оракул
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 710
Cпасибо сказано: 93
Спасибо получено:
353 раз в 297 сообщениях
Очков репутации: 71

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 18:35 
Не в сети
Продвинутый
Зарегистрирован:
22 дек 2018, 17:13
Сообщений: 74
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Кстати, для двух чисел определить невозможно - всего одно уравнение (суммы самих с собой не рассматриваются)
х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 число заданных чисел.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 05 мар 2019, 11:21 
Не в сети
Продвинутый
Зарегистрирован:
21 июл 2016, 07:08
Сообщений: 98
Cпасибо сказано: 7
Спасибо получено:
15 раз в 12 сообщениях
Очков репутации: 3

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 08 мар 2019, 10:34 
Не в сети
Продвинутый
Зарегистрирован:
21 июл 2016, 07:08
Сообщений: 98
Cпасибо сказано: 7
Спасибо получено:
15 раз в 12 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Я нашла вариант решения предложенной задачи. Я технолог, а технологи все проверяют экспериментально. Для чистоты эксперимента попарные суммы чисел должен посчитать кто-то другой. Но приходится считать самой. Задаем следующие числа: х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 входит в четверку самых больших попарных сумм.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 09 мар 2019, 10:57 
Не в сети
Оракул
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 710
Cпасибо сказано: 93
Спасибо получено:
353 раз в 297 сообщениях
Очков репутации: 71

Добавить очки репутацииУменьшить очки репутации
Предложу упорядоченный набор из 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;

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 11 мар 2019, 00:21 
Не в сети
Оракул
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 710
Cпасибо сказано: 93
Спасибо получено:
353 раз в 297 сообщениях
Очков репутации: 71

Добавить очки репутацииУменьшить очки репутации
Алгоритм дешифровки по попарным суммам:
/*Заданная матрица-строка из попарных сумм*/
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 "Ошибка: числа в матрице не являются попарными суммами нескольких чисел";

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Восстановить функцию

в форуме Комплексный анализ и Операционное исчисление

Ryslannn

1

238

22 мар 2014, 13:52

Восстановить равенство

в форуме Алгебра

nastya_grigorenko

3

592

07 сен 2013, 15:45

Как восстановить середину шестиугольника

в форуме Геометрия

NakaNaka

1

204

28 авг 2013, 10:13

Восстановить аналитическую функцию

в форуме Комплексный анализ и Операционное исчисление

karinakarina

1

186

13 мар 2017, 22:16

Восстановить аналитическую функцию

в форуме Комплексный анализ и Операционное исчисление

Sasha95

1

321

09 ноя 2013, 14:27

Восстановить аналитическую функцию

в форуме Комплексный анализ и Операционное исчисление

hummel

4

388

20 фев 2012, 19:33

Восстановить аналитическую функцию

в форуме Комплексный анализ и Операционное исчисление

grimlok2013

5

303

20 дек 2015, 11:01

Восстановить аналитическую функцию f(z)

в форуме Комплексный анализ и Операционное исчисление

sfanter

1

277

29 май 2016, 12:29

Восстановить аналитическую функцию

в форуме Комплексный анализ и Операционное исчисление

gigsKA

26

4221

25 мар 2013, 15:57

Восстановить аналитическую функцию f (z)

в форуме Комплексный анализ и Операционное исчисление

csacsa

3

944

19 дек 2014, 23:07


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved