Таблицы Брадиса

Вместо полного доказательства мы покажем,

Вместо полного доказательства мы покажем,

Математическое просвещение - Винберг Э. Б

Действительно, если А не содержит В (в частности, если |А| ^ |В|), то В содержит элемент г, не входящий в А, т. е. аА(/В) = 0.

С другой стороны,

ЛМ. Таким образом, за 16 = 24 попыток Витя может разгадать тест не только из 30, но даже из 33 = 4 ■ 23 + 1 вопросов. Возник­ло естественное желание уменьшить число попыток до 15, а также научиться строить достаточно длинные разрешимые системы в про­странствах любой размерности. Ещё через несколько дней я понял, что последняя задача сводится к теореме 1.

Теорема о разрешимых системах

Пусть S2 (n) — сумма цифр в двоичной записи числа n, а B(n) = = Et-/ S2(i). В частности, B(2m) = m ■ 2m-i. [48]

Теорема 2. В n-мерном пространстве имеется разрешимый набор длины B (n) + 1.

Вместо полного доказательства мы покажем, как из построенного в тео­реме 1 разрешимого набора длины 13 в 8-мерном пространстве получить разрешимые наборы в 7-, 6- и 5-мерном пространствах (длины соответ­ственно 10, 8, 6). Действия в общем случае совершенно аналогичны.

Построенный набор длины 13 = В(8) + 1 состоял из функций (8-мерных векторов)

£3 £2 £1 £2 £1 £2 £1 £2 £ 1 £ £ £ £

/1 , А , /2 , /2 , /3 , /3 , /1,2, /1,3, /2,3, /1,2,3

и соответствующих функционалов

а, а, а, а1, а1, а2, а2, ^3, а3, ^1,2, ^1,3, ^2,3.

Значение функции в точке (-1, -1, -1) было нужно только для вычис­ления функционала а. Остальные функционалы можно рассматривать на 7-мерном пространстве функций, определённых на оставшихся 7 точках. Ограничив все наши функции (кроме первых трёх) на эти 7 точек, мы по­лучим разрешимый набор 7-мерных векторов $2, ${, д|, $2, д|, $д, $1,2, $1,3, $2,3, $1,2,3 длины 10 с функционалами а1, а1, а2, а2, а3, а3, а1,2, а1,3, а2,3. При этом длина набора уменьшится на 3 = £2(7). Поэтому число функций с В(8) + 1 уменьшилось до В(7) + 1.