Дополню
Deerenaros : Оптимальное решение -
Folded Reed—Solomon Code, который к тому же подозрительно похож на условие задачи. С использованием этого алгоритма каждому заключённому необходимо запомнить помимо своего O(1/ε) частей кода, где ε - отношение остающихся заключенных к общему, 1/ε округляем вверх для необходимой избыточности.
Как оно работает - из исходных пар составляется код Рида-Соломона размером 1000*(1+O(1/ε)) букв (размер буквы в битах исходя из размера данных, присваемых числах, в задаче это 6 бит), каждый заключенный помимо исходной пары со своим номером запоминает части кода на местах
1000εn ... 1000ε(n+1)-1, n - свой номер. Минимальная выборка в виде заключенных с номерами 1..1000ε даст 1000ε своих пар, 1000 кусков кода и пару 1000-го, что больше минимально необходимых 1000ε+1.
В изначальном варианте: ε=¼, О(1/ε)=4, код размером 1000*(1+4)=5000 букв, устойчивость FRS-кода - до
n*(1-ε)-1=3999 потерь, тогда как мы теряем только 3749. Для ε=⅒ им придётся запоминать 10 кусков кода, для ε=¾ - один (как и для ∀ε>½). Если количество заключенных увеличить, то пусть заключенные с одинаковыми номерами будут запоминать разные части кода: например один как уже определили, второй со сдвигом на 10 от своего номера; в таком случае код можно поровну распределить на всех и число частей для запоминания уменьшится нацело вдвое.
