Доказать гипотезу.

[main.c]

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

Задача :
Имеются два целочисленных массива из 8 элементов. Числа могут повторяться.
Для тех кто не знаком с массивами, массив - это упорядоченная последовательность элементов одной природы.
Пример:
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Если из одного массива можно получить другой, путём перестановки элементов, вывести yes.

Но суть не в этом. Суть в том, что я утверждаю: если сумма элементов первого массива равна сумме элементов второго массива и одновременно с этим условием, произведение элементов первого равно произведению элементов второго, эти массивы состоят из одних и тех же чисел.
Как мне это доказать?

[gris]

-1 2 4 0 5 7 1 6
-3 2 6 0 9 1 3 6
Сумма и произведение одинаковы.
Ужесточайте требования к массивам.

[main.c]

Допустим было бы требование, что "0" в массиве нет.

Даже не так, требования остаются те же, целочисленный массив. Но после подсчёта сумм, заменим все "0" на "1". И после этого проверим равенство произведений.

[EtCetera]

Тогда $1,-1,1,-1,1,-1,2,2$.

[main.c]

EtCetera в сообщении #621332 писал(а):

Тогда $1,-1,1,-1,1,-1,2,2$.

А где второй массив?)

[gris]

2 2 -2 -2 4 4 -4 -4
1 1 -1 -1 8 8 -8 -8

[EtCetera]

Извиняюсь, не вчитался в условие. Тогда тут даже отрицательные не нужны.
$1,1,1,1,1,2,2,9$ и $1,1,1,1,1,1,6,6$.

[main.c]

gris в сообщении #621335 писал(а):

2 2 -2 -2 4 4 -4 -4
1 1 -1 -1 8 8 -8 -8

Этим примером Вы разбили мою гипотезу напрочь Жаль.
Эту задачу можно решить и в лоб, просто найти каждому элементу свою пару, если не найдётся, то значит такой перестановки не существует. НО хотелось бы найти более изысканное решение. Может быть всё-таки есть какой-нибудь математический способ решения этой задачи?

[gris]

Можно отсортировать, потом поэлементно сравнить. Но так, как Вы сказали даже быстрее. Только надо как-то помечать найденные элементы во втором массиве. Переставлять их вперёд.

[ИСН]

Sounds like $O(N^2)$.

[Xaositect]

ИСН в сообщении #621347 писал(а):

Sounds like $O(N^2)$.

На массивах из 8 элементов действительно быстрее. Там сортировка меньше, чем за 16 сравнений не делается.

-- Чт сен 20, 2012 13:18:41 --

Кстати, если хочется все-таки поскладывать и поумножать, то можно вычислить все элементарные симметрические многочлены и сравнить их.

[main.c]

gris в сообщении #621344 писал(а):

Можно отсортировать, потом поэлементно сравнить. Но так, как Вы сказали даже быстрее. Только надо как-то помечать найденные элементы во втором массиве. Переставлять их вперёд.

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

[gris]

Ну тогда типа каждый с каждым. Дополнительный массив понадобится, хоть булевский.
Зато одни сравнения. А то умножать да складывать. На все многочлены тыща умножений и тыща сложений. Да ещё 8 сравнений.

[ewert]

gris в сообщении #621352 писал(а):

Дополнительный массив понадобится, хоть булевский.

Не обязательно. Если элементы массивов положительны, то для их вычёркивания достаточно приписывать им минусы. Потом при желании массивы можно и восстановить.

Если произвольного знака, то задача сводится к предыдущей, если найти минимальный элемент и вычесть его значение минус один из каждого. В общем, снять кастрюлю, вылить воду, налить воду, поставить на плиту...

[Cash]

Вместо произведения элементов можно использовать сумму квадратов и кубов. В практическом смысле совпадения трех сумм вполне достаточно. Достаточно ли этого теоретически? Интересно будет поискать контрпример.