Из какой области дискретной математики задача?

[provincialka]

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

Вот задача (из вступительной олимпиады в ШАД)

Кодовый замок состоит из 3 цифр, каждая из которых принимает значения от 1 до 8. Ключ (также из 3 цифр) открывает замок, если совпадают хотя бы две цифры. Какое наименьшее число ключей открывает любой замок?

Текст пишу по памяти, но, думаю, идея ясна: в кубе $8\times 8\times 8$ нужно выбрать наименьшее подмножество так, что любая точка куба находится на расстоянии не более $1$ от этого подмножества. Расстояние берется по Хэммингу.

Подозреваю, что такое множество может даже иметь название...

[wrest]

(Оффтоп)

А задача-то решилась?
Я бы рассуждал так. Всего может быть $512$ разных ключей.
К одному любому замку подходят $7\cdot 3+1 =22$ различных ключа. Или, что тоже самое, один любой ключ открывает $22$ разных замка.
Вероятность открыть конкретный замок случайным ключом равна $22/512$
Тогда потребуется $\lceil 512/22 \rceil=24$ или больше ключей.

[worm2]

https://en.wikipedia.org/wiki/Covering_code
Вот тут пишут, что $K_8(3,1)=32$ и ссылаются на какую-то статью "Kalbfleisch–Stanton, 1969". Возможно, имеется в виду вот эта.

Что-то меня совершенно не удивляет, что "с налёту задача не решилась"

[mihaild]

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

[maxal]

mihaild в сообщении #1301238 писал(а):

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

Да, это почти что задача теории кодирования. В идеале каждый замок должен открываться ровно одним элементом подмножества, и тогда искомое подмножество образовывало бы 1-error correcting code длины 3 над полем $\mathrm{GF}(8)$. Проблема только в том, что мы не в идеальном мире.

[provincialka]

wrest
Ребята, которые мне эту задачу рассказали, добились множества из 56 ключей (ну, по их словам).
Вашу оценку мы, конечно, тоже получили, но она явно занижена. Потому что предполагает, что существуют 24 ключа с непересекающимися окрестностями (по Хэммингу) радиуса 1. Но таких существует только 8.
Действительно, если два ключа имеют совпадение в одной позиции, скажем $(1,2,3)$ и $(1,4,5)$, то меняя одну позицию, мы получим два замка, открываемые обоими ключами, а именно, $(1,2,5)$ и $(1,4,3)$ , то есть 1-окрестности этих ключей имеют пересечение размера 2. Совсем не пересекаются окрестности только таких ключей, у которых никакие два элемента не совпадают. А таких, естественно, не более 8.

Надо бы поискать исходный текст задачи... Давать такое на экзамене.. Слишком жестоко!

-- 02.04.2018, 22:28 --

worm2 в сообщении #1301237 писал(а):

Что-то меня совершенно не удивляет, что "с налёту задача не решилась"

Спасибо! Вы вернули мне веру в себя

Завтра, надеюсь, встречусь со студентами (если не проспят пару! ) Как хорошо, что у нас есть такие, интересующиеся и знающие! Бальзам на душу преподавателя...

[mserg]

А что тут думать?
Ответ - 32 ключа:

1, 1, 1
1, 5, 6
1, 7, 8
1, 8, 5
2, 2, 4
2, 3, 2
2, 4, 7
2, 6, 3
3, 2, 7
3, 3, 3
3, 4, 2
3, 6, 4
4, 2, 2
4, 3, 4
4, 4, 3
4, 6, 7
5, 1, 6
5, 5, 1
5, 7, 5
5, 8, 8
6, 1, 8
6, 5, 5
6, 7, 6
6, 8, 1
7, 2, 3
7, 3, 7
7, 4, 4
7, 6, 2
8, 1, 5
8, 5, 8
8, 7, 1
8, 8, 6

[provincialka]

А доказательство минимальности? И сколько нужно времени, чтобы найти этот пример?

[mserg]

От прочтения условий до получения результата и доказательства оптимума потребовалось примерно минут 30.

Скорее всего, некоторые догадались, что эта задача о покрытии была сведена к (целочисленному) линейному программированию и была решена численно с доказательством оптимума.

Так что я не обманул, на счет того "а чего тут думать?"

Судя по знакомым словам, наводки на аналитические оценки дал worm2. У него и оптимум указан - 32.

[provincialka]

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

[vpb]

Вот как доказать нижнюю оценку вручную.

Допустим, у нас есть всего два ключа, у которых на первом месте находится $1$, скажем $1ab$ и $1cd$. Тогда любой замок вида $1ef$, где $e\ne a,c$, $f\ne b,d$, находится от каждого из этих двух ключей на расстоянии $\geq2$. Поэтому должен существовать ключ вида $xef$, $x\ne1$. Таким образом, должно быть не менее $36$ ключей, у которых в первой позиции стоит не $1$. Получается всего $\geq38$ ключей.

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

Ниже покажем, что на самом деле, если для некоторой пары (цифра, позиция) есть ровно три ключа, то всего ключей
не менее $34$. Выведем отсюда нужную оценку. В силу допущения, можно считать, что всегда есть по крайней мере 4 ключа, имеющих данную цифру в данной позиции. Теперь воспользуемся приемом двойного подсчета. А именно, подсчитаем число троек (цифра, позиция, ключ), для которых данный ключ имеет данную цифру в данной позиции. С одной стороны, таких троек $3N$, где $N$ --- число ключей. С другой стороны, есть $8$ цифр, три позиции, и для данных цифры и позиции есть $\geq4$ ключей, значит всего троек $\geq 3\cdot8\cdot4=96$, откуда $N\geq32$.

Остается показать, что если для некоторой позиции и цифры есть всего три ключа, то всего ключей $\geq34$. Производя перестановки и перенумерации, можно считать, что рассматривается позиция $1$, цифра $1$. Пусть три ключа $1a_1a_2$, $1b_1b_2$, $1c_1c_2$. Сначала будем рассматривать случай, когда $a_1$, $b_1$, $c_1$ попарно различны, и $a_2$, $b_2$, $c_2$ тоже. Перенумеровывая цифры, можно считать, что рассматриваемые три ключа --- это $111$, $122$ и $133$. Будем их называть ключами типа А.

То же рассуждение, что и выше, показывает, что для каждой пары $(a,b)$ с $4\leq a,b\leq8$ существует ключ вида $xab$ с $x\ne1$. Будем их называть ключами типа Б. Их по крайней мере 25.

Пусть $X$ --- множество всех замков вида $xab$, где $x\ne1$, $a,b=1,2,3$, $a\ne b$. Ясно, что ни один такой замок не открывается ни одним из ключей типов А или Б. Поэтому нам достаточно показать, что любое множество $Y$ ключей, открывающее любой замок из $X$, содержит по крайней мере 6 ключей (отметим, что множество из 6 ключей существует,
это $Y_0=\{112, 113, 121, 123, 131, 132\}$). Если для любой цифры $2,3,\ldots,8$ есть ключ из $Y$ с данной первой цифрой, то ясно, что $|Y|\geq7$. В противном случае можно предполагать, что $Y$ не содержит ключей, начинающихся с $8$. Пусть $a,b=1,2,3$, $a\ne b$. Поскольку $Y$ содержит ключ, открывающий $8ab$, этот ключ непременно должен иметь
вид $xab$. Значит, для любых $a,b$ с указанными условиями $Y$ содержит ключ, заканчивающийся на $ab$. Отсюда $|Y|\geq6$.

Таким образом, случай, когда все $a_1$, $b_1$, $c_1$ попарно различны, и $a_2$, $b_2$, $c_2$ тоже, разобран. Остальные случаи аналогичны. Более точно, пусть $p=|\{a_1,b_1,c_1\}|$, $q=|\{a_2,b_2,c_2\}|$. Можно считать, что $(p,q)$ --- одна из пар $(1,3)$, $(2,2)$, $(2,3)$. Ключей типа Б есть по крайней мере $(8-p)(8-q)$. Поэтому при $(p,q)=(1,3),(2,2)$ ключей всего по крайней мере 38. Пусть $(p,q)=(2,3)$, тогда ключей типа Б по крайней мере 30. Кроме того, множество $X$ непусто, поэтому есть еще по крайней мере один ключ.

-- 03.04.2018, 15:34 --

Теперь построим пример с 32 ключами.

Пусть $I$ --- множество из 4-х элементов, скажем $I=\{1,2,3,4\}$. Легко видеть, что в "кубе" $I\times I\times I$ есть подмножество $S$ из 16 точек такое, что его проекция на каждую координатную плоскость сюръективна. Например, $S=\{(x,y,z)\mid x+y+z\equiv 0\pmod4\}$.

Пусть $I_1=\{1,2,3,4\}$, $I_2=\{5,6,7,8\}$, $S_1$ --- подмножество указанного типа в $I_1\times I_1\times I_1$, $S_2$ --- в $I_2\times I_2\times I_2$. Тогда $S_1\cup S_2$ можно взять в качестве множества ключей (легко видеть, что).

Область эта называется "комбинаторные схемы", или "блок-схемы", или "конечные геометрии", combinatorial designs, block designs, finite geomeries.

[maxal]

vpb в сообщении #1301436 писал(а):

Область эта называется "комбинаторные схемы", или "блок-схемы", или "конечные геометрии", combinatorial designs, block designs, finite geomeries.

Не совсем. В указанных областях блоки являются множествами, т.е. неупорядоченными наборами. В рассматриваемой же задаче речь идет об упорядоченных наборах (3-разрядных ключах).
Я думаю, теория кодирования здесь всё-таки ближе.

[vpb]

maxal в сообщении #1301443 писал(а):

Я думаю, теория кодирования здесь всё-таки ближе

Да, я хотел тоже упомянуть и её, да как-то не. Эти вопросы вообще часто вместе трактуются, см. например П.Камерон, Дж. ван Линт, Теория графов, теория кодирования, и блок-схемы.