восстановить действие программы

[lenamizd]

В ЭВМ заложена программа, в соответствии с которой любой набор из 10 символов переставляется в определенном порядке, одном и том же для всех наборов. Какое наименьшее число наборов из нулей и единиц нужно составить, чтобы по результатам работы с ними ЭВМ можно было бы однозначно восстановить действие программы? Что это за наборы?

[ИСН]

Ой, 10 - это очень много, далеко за пределами человеческих возможностей. Давайте будет 2. Вот наборы из 2 символов. С ними всё понятно?

-- Пн, 2011-09-26, 13:58 --

Ах, мы не в разделе "помогите решить". Тогда так. Вот 10 наборов: у каждого одна единица (у всех в разной позиции), остальные нули. Этого точно хватит. Теперь подумаем, можно ли меньше.

[lenamizd]

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

Ой, 10 - это очень много, далеко за пределами человеческих возможностей. Давайте будет 2. Вот наборы из 2 символов. С ними всё понятно?

-- Пн, 2011-09-26, 13:58 --

Ах, мы не в разделе "помогите решить". Тогда так. Вот 10 наборов: у каждого одна единица (у всех в разной позиции), остальные нули. Этого точно хватит. Теперь подумаем, можно ли меньше.

Конечно, можно

[Shadow]

Четыре должно хватить (даже за 16). Записываем в двоичном виде числа от 1 до 10
0001 - 1
0010 - 2
.......
1010 - 10
В колоннах будут наши ключи. Подаем их последовательно на вход. На выходе получим их номера в двоичном виде.

[lenamizd]

Shadow в сообщении #486563 писал(а):

Четыре должно хватить (даже за 16). Записываем в двоичном виде числа от 1 до 10
0001 - 1
0010 - 2
.......
1010 - 10
В колоннах будут наши ключи. Подаем их последовательно на вход. На выходе получим их номера в двоичном виде.

Необходимо еще доказать, что трех не достаточно.

[TOTAL]

lenamizd в сообщении #486601 писал(а):

Необходимо еще доказать, что трех не достаточно.

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

[Shadow]

TOTAL в сообщении #486776 писал(а):

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

Но это так только если принять, что наш алгоритм оптимален. Вообще надо доказать, что n попытками можно однозначно определить не больше $2^n$ элементов.
Класический вариант этой задачи:
В одной комнате есть 1000 ключей, включающих 1000 лампочек в другой комнате. Какое минимальное число прогулок между комнат для однозначного определения какой ключ с какой лампочкой связан.

[TOTAL]

Shadow в сообщении #486780 писал(а):

TOTAL в сообщении #486776 писал(а):

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

Но это так только если принять, что наш алгоритм оптимален.

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

[Shadow]

Сейчас Вас понял. После первой попытки будут хотя бы 5 одинаковых бита. Если рассматривать толко их, после второй будут хотя бы 3 одинаковых, после третьей - хотя бы 2. Т.е хотя бы 2 элемента отобразатся одинаково

[TOTAL]

Shadow в сообщении #486792 писал(а):

Сейчас Вас понял. После первой попытки будут хотя бы 5 одинаковых бита.

Совсем не то.
Запишите каждую из попыток одну за другой как столбец из 0 и 1. Обязательно найдутся две одинаковых строки. Например, первая строка и вторая. Отображение может быть таким, что первый элемент переходит в первый, а второй во второй. Но может быть и таким, что первый элемент переходит во второй, а второй в первый. Отличить невозможно.

[Shadow]

Цитата:

Совсем не то..

Как раз то.

Цитата:

Обязательно найдутся две одинаковых строки.

Я объяснил почему найдутся.