РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 7660 Добавить в вариант

Каждому из четырех абонентов A₁, A₂, A₃, A₄ надо выдать по два уравнения вида $a w плюс b x плюс c y плюс плюс d z=t,$ где $a, b, c, d, , t, w, x, y, z принадлежит левая фигурная скобка 0, 1 правая фигурная скобка .$ Значения секретных битов w, x, y, z одинаковы для всех абонентов и им заранее неизвестны. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара {A₁, A₃}, {A₁, A₄}, {A₂, A₃} могла достоверно вычислить w, x, y, z, но чтобы при этом: 1) ни одна другая пара абонентов не могла бы достоверно вычислить более одного секретного бита; 2) ни один абонент в одиночку не был в состоянии достоверно вычислить даже один секретный бит. Например, если абонент A₁ получит уравнения

$левая фигурная скобка w плюс x плюс y плюс z=1; w плюс x плюс 0 умножить на y плюс 0 умножить на z=1 правая фигурная скобка ,$

a A₂

$левая фигурная скобка w плюс 0 умножить на x плюс y плюс 0 умножить на z=0; w плюс x плюс 0 умножить на y плюс плюс z=0 правая фигурная скобка .$

Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что $w=1,$ $x=0,$ $y=1,$ $z=1.$ При этом будем говорить, что пара абонентов {A₁, A₂} может достоверно вычислить секретные биты w, x, y, z. Здесь традиционно полагается, что $1 плюс 1=0.$

Спрятать решение

Решение.

Пусть w₀, x₀, y₀, z₀ значения секретных битов w, x, y, z. Решим прежде задачу, предполагая, что все секретные биты равны нулю: $w_0=x_0=y_0=z_0=0.$ Затем в уравнениях можно будет сделать замену

$w arrow w плюс w_0,$ $\ldots,$ $z arrow z плюс z_0$

и тем самым получить решение задачи в общем случае.

Запишем теперь какую-нибудь систему из четырех уравнений, которой удовлетворяют только нулевые значения. Например,

$w плюс x=0, \quad левая круглая скобка 1 правая круглая скобка$ $x плюс y=0, \quad левая круглая скобка 2 правая круглая скобка$ $y плюс z=0, \quad левая круглая скобка 3 правая круглая скобка$ $w плюс x плюс y=0. \quad левая круглая скобка 4 правая круглая скобка$

Запишем еще одно уравнение, сложив эти четыре:

$x плюс y плюс z=0. \qquad левая круглая скобка 5 правая круглая скобка$

Система из любых четырех уравнений из набора (1)−(5) имеет только нулевое решение.

Далее идея в следующем. Если пара абонентов должна уметь находить все биты, то этой паре выдадим четыре различные уравнения из набора (1)−(5), если же нет, то хоть одно уравнение у этой пары должно быть общим.

Замечание.

Здесь нет четких алгоритмов и успех заранее не гарантирован. Возможно, следовало выбрать какие-то другие уравнения (1)−(4). Заметим, например, что абонентам, которые не должны уметь находить секрет, нельзя выдать уравнения (1), (2) и (4), так как значение бита z они не найдут, но определят, что $w=x=y=0,$ а это по условию недопустимо. Никакому абоненту нельзя выдать уравнения (2) и (5), так как из них следует, что $z =0.$

Абонентам раздать уравнения можно так: A₁: (1), (2); A₂: (1), (5); A₃: (3), (4); A₄: (4), (5). Выполнив замену, запишем ответ в общем случае.

Ответ: например,

$A_1: w плюс x=w_0 плюс x_0, x плюс y=x_0 плюс y_0 ;$ $A_2: w плюс x=w_0 плюс x_0, x плюс y плюс z=x_0 плюс y_0 плюс z_0;$ $A_3: y плюс z=y_0 плюс z_0, w плюс x плюс y=w_0 плюс x_0 плюс y_0;$ $A_4: w плюс x плюс y=w_0 плюс x_0 плюс y_0, x плюс y плюс z=x_0 плюс y_0 плюс z_0.$

Межрегиональная олимпиада школьников им. И. Я. Верченко, 11 класс, 2 тур (заключительный), 2020 год

Классификатор: Разное. Логические уравнения

Спрятать решение · Помощь