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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 00:24 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 14:00 
Не в сети
Продвинутый
Зарегистрирован:
22 дек 2018, 17:13
Сообщений: 93
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 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 15:10 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 24 фев 2019, 18:35 
Не в сети
Продвинутый
Зарегистрирован:
22 дек 2018, 17:13
Сообщений: 93
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
Сообщений: 142
Cпасибо сказано: 9
Спасибо получено:
19 раз в 16 сообщениях
Очков репутации: 3

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Восстановить числа по их попарным суммам
СообщениеДобавлено: 08 мар 2019, 10:34 
Не в сети
Одарённый
Зарегистрирован:
21 июл 2016, 07:08
Сообщений: 142
Cпасибо сказано: 9
Спасибо получено:
19 раз в 16 сообщениях
Очков репутации: 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 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

Добавить очки репутацииУменьшить очки репутации
Предложу упорядоченный набор из 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 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

Добавить очки репутацииУменьшить очки репутации
Алгоритм дешифровки по попарным суммам:
/*Заданная матрица-строка из попарных сумм*/
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пасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3, 4  След.  Страница 1 из 4 [ Сообщений: 40 ]

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

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

demon_666

1

200

16 окт 2022, 17:32

Как восстановить решение?

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

alekscooper

6

203

16 окт 2019, 18:08

Восстановить группу Ли по алгебре Ли

в форуме Линейная и Абстрактная алгебра

nosurnamename

4

160

24 окт 2023, 13:42

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

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

Marry

1

478

04 июн 2018, 11:34

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

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

honey

0

191

06 дек 2020, 22:30

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

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

karinakarina

1

476

13 мар 2017, 22:16

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

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

Veltare

3

474

30 ноя 2017, 12:38

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

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

sfanter

1

624

29 май 2016, 12:29

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

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

grimlok2013

5

570

20 дек 2015, 11:01

Восстановить оригинал по изображению F p

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

SPAC_E

0

109

22 окт 2019, 15:38


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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


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

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

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

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