fso/2l + fsi/2] < So, за исключением случая, когда «о = 2fc + 1 и si = 2/г - 1. В последнем случае, однако, fft(so) + fft-i(so) + ff(-i(si) > Ы{2к + 1) + 2ht-ii2k) > ht(2k) + 2ht-i{2k).

(b) Заметьте, что множество S, содержащее числа О, 1, ..., s - 1 в двоичной записи, имеет такое свойство: Sol) Si = 5о и So содержит \so/2] элементов. Отсюда следует, что /((2"-",т) = [г] (1 + 2)"(1 + 2гГ-".

10. (а) Должно существовать gt)(t) - 1) троек, и Xv должно встречаться в t) из них. (Ь) Поскольку V нечетно, для каждого i имеется уникальная тройка {xi,yj,z}, откуда легко показать, что S - Штейнеровская система троек. Отсутствующие в К пары - {z,X2}, {Х2,У2}, {У2,хз}, {хз,уз}, {xv-i,yv-i}, {xv,z}. (d) Начав со случая для d = 1 и применив операции d -> 2t) - 2, d -> 2f +1, получим все неотрицательные числа, которые не имеют вид ЗА; + 2, потому что случаи 6к + (0,1, 3,4) получаются из меньших чисел Зк + (1,0,1, 3) соответственно.

Оказывается, "Штейнеровские системы троек" не должны именоваться Штейнеров-скими, хотя это имя глубоко укоренилось в литературе. Публикация Штейнера [СгеЛе 45 (1853), 181-182] появилась несколькими годами позже публикации Киркмана. Феликс Клейн (Felix Klein) заметил [Voriesungen iiber die EntwicJdung der Math, im 19. Jahrhundert 1 (Springer, 1926), 128], что в последние годы жизни Штейнер цитировал английских авторов без ссылок на них. Более того, концепция троек появилась еще раньше в двух хорошо известных книгах Ю. Плюкера (J. РШскег) [System der anaiytischen Geometrie (1835), 283-284; Theorie der algebraischen Curven (1839), 245-247].

11. Возьмем Штейнеровскую систему троек над 2i; + 1 объектами. Назовем один из объектов 2, а другие объекты переименуем таким образом, чтобы тройками, содержащими 2, оказались {z, Xi, Xi}. Затем удалим эти тройки.

12. {к, {к+1) mod 14, {к+4) mod 14, (к+б) mod 14} при О < А: < 14, где {к + 7) mod 14 представляет собой дополнение к (комплементарная система является частным случаем групп, разделяемых на блоки; см. Bose, Shrikhande, and Bhattacharya, Ann. JVfath. Statistics 24 (1953), 167-195).

14. Самый простой вид удаления - из A:-d-дepeвьeв (замещение для корня может быть найдено примерно за 0(iV~") шагов). В четревьях для удаления, похоже, потребуется полная перестройка поддерева, корнем которого является удаляемый узел (однако такое поддерево содержит в среднем лишь около logiV узлов). Для почтовых деревьев удаление практически безнадежно.

16. Пусть каждая тройка соответствует кодовому слову и каждое кодовое слово имеет ровно три равных единице бита, определяющих элементы соответствующей тройки. Если и, V и W - различные кодовые слова, то слово и имеет не более двух равных единице битов с суперпозицией v и w, поскольку оно может иметь не более одного общего бита со словами D и п; по отдельности (аналогично из системы четверок порядка v можно построить v{v - 1)/12 кодовых слов, никакое из которых не содержится в суперпозиции любых трех других, и т. д.).

17. (а) Пусть Со = 6о, а для 1 < к < п положим Ск = (если bk-i = О, то "*" иначе - 6*), с-к = (если Ьк-1 = 1, то "*", иначе - Ьк). Тогда базовый запрос с-п . ..со . ..Сп описывает содержимое блока 6о ... Ьп- (Следовательно, эта схема представляет собой частный случай комбинаторного хеширования и ее среднее время запроса соответствует нижней границе в упр. 8, (Ь).)

(Ь) Пусть dk = [бит к определен] для -п < А; < п. Можно положить, что d-k < dk при 1 < А: < п. Тогда максимальное количество проверенных блоков получается, когда все определенные биты равны нулю и оно может быть вычислено следующим образом.

м.-{1 ;), м,-(11). м,.(11).

и, наконец, выведем х (который может равняться у после к = 0).

Будем говорить, что (х,у) У (х,у), если х > х и х + у > х + у. Тогда, если (х,у) >: (х,у), имеем (x,y)Md > (x,y)Md для d = О, 1, 2. Теперь

(х,у)М2М(Мо = {Fj+3X,Fj+3x),

ix,y)MiM(Mi = (F;+3X + F,+2y,Fj+2X + Fj+iy),

(х, у)МоМ(М2 = (Fj+2X + F,+2y, Fj+2X + Fj+2y);

следовательно, (x,y)MiM(Mi У {х,у)М2М(Мо, потому что 2у > х; и аналогично (x,y)MiMfMi >: (х,у)МоМ(М2, потому что х > у. Отсюда вытекает, что наихудший случай возникает либо при d-k + dk < 1 для 1 < к < п, либо при d-k + dk > 1 для 1 < к < п. Кроме того,

{х,у)МоМ( = (Fj+ax + Fj+iy,Fj+ix + F,+iy),

(х,у)М(Мо = (Fj+2X + Fj+iy,Fj+2X + Fj+iy),

(x,y)M2M{ ={Fj+2X,Fj+ix), ,

{x,y)M(M2 = (Fj+ix + Fjy,Fj+ix + Fjy).

Значит, в худшем случае требуется следующее количество блоков:

2"-Ft+3, если 0<t<n [из МШо"];

2""F3„-2(+3, если n<t< \Зп/2] [из Mf"-2(MiM2)-"Mo];

2"+-, если 13п/2] < t < 2п [из MiMiMif-Mo].

[Эти результаты, по сути, были получены В. О. Буркхардом (W. А. Burkhard), BIT 16 (1976), 13-31, и обобщены в J. Сотр. Syst. Sci. 15 (1977), 280-299; более сложное отображение Буркхарда из ао ... агп на 6о •. • 6„ было упрощено здесь согласно предложению П. Дубоста (Р. Dubost) и Ж.-М. Труссе (J.-M. Trousse), доклад STAN-CS-75-511 (Stanford Univ., 1975).]

18. (а) Всего .имеется 2"(т - п) символов "*" следовательно, 2"п цифр с 2"n/m цифр в каждом столбце. Половина цифр в каждом столбце должна быть равна нулю. Значит, 2"~п/т - целое и в каждом столбце содержится (2"~n/m) несоответствий. Поскольку каждая пара строк имеет минимум одно несоответствие, необходимо получить 2" (2" -1)/2 < (2"-n/m)2m.

(b) Рассмотрим 2" m-битовых чисел с нулем в тп-п определенных столбцах. Половина из них имеет нечетный паритет. Число строк с четным паритетом среди строк с символом "*" в любом из неопределенных столбцов равно числу строк с нечетным паритетом.

(c) *00 0, *11 1, 0*10, 1*10, 00*1, 10*1, 010*, 110*. Это построение не такое равномерное, как (13), поскольку запрос типа *01* подходит к четырем строкам, в то время как *10* - только к двум. Заметьте, что (13) имеет циклическую симметрию.

(d) Постройте 4 строк из каждой строки (13) путем замещения каждого символа "*" символами "* * * *", каждого нуля - любой из первых четырех строк и каждой единицы - любой из последних четырех строк (подобное построение создает ABD(mm, пп) из любых ABD(m,n) и ABD(m,n)).

(e) Пусть дано ABD(16,9). Можно в каждой строке заключить в кружок один символ "*" таким образом, чтобы в каждом столбце было равное число заключенных в кружки

символов "*" Затем можно разбить каждую строку на две строки, заменяя заключенные в кружки элементы нулями и единицами. Для того чтобы показать, что такая процедура заключения символов "*" в кружки возможна, заметим, что символы "*" в каждом столбце могут быть произвольно разделены на 32 группы по 7 в каждой; тогда 512 строк содержат символы "*" из 7 различных групп каждая и каждая из 32 х 8 = 512 групп появляется в 7 различных строках. Теорема 7.5.1Е ("теорема о свадьбе") гарантирует существование идеального соответствия одного зацикленного элемента в каждой строке и в каждой группе.

Литература. R. L. Rivest, SICOMP 5 (1976), 19-50; А. Е. Brouwer, Combinatorics, edited by Hajnal and Sos, CoUoq. Math. Soc. Janos Bolyai 18 (1978), 173-184. Брувер доказывает, что ABD(2n, n) существует для всех п > 32. Метод из п. (d) дает нам также ABD(32,15) путем комбинирования (13) и (15).

19. Согласно упр. 8 среднее количество при &-к определенных битах равно 2*~/8 fc(8, 8)/ /(*) со значениями соответственно (32,22, ifi,f,f,f,,f,l)a (32, 22,14.9,9.9,6.4,4.1, 2.6,1.6,1) для 8 > А; > 0. Эти значения лишь несущественно больше значений 32*/* а (32, 20.7,13.5, 8.7, 5.7, 3.7, 2.4,1.5,1). Значения для наихудшего случая равны (32, 22,18,15,11, 8,4,2,1) (примерами "наихудших запросов" могут служить ********, о******», *о****0*, ♦ ♦0**0*1, **0*00*1, *0**0100, 0001**10, 000000*0, 00000000).

20. В работе J. А. La Poutre, Disc. Math. 58 (1986), 205-208, показано, что ABD(m,n) не может существовать при m > (j) и п > 3; следовательно, ABD(16,6) не существует. В работе La Poutre and van Lint, Util. Math. 31 (1987), 219-225, доказано, что не существует ABD(10,5). ABD(8,6) получаем из ABD(8,5) или ABD(4,3), используя метод из упр. 18. Таким образом получается несколько неизоморфных решений, и могут существовать и другие примеры ABD(8,6). Единственные остающиеся возможности (кроме тривиальных ABD(5,5) и ABD(6,6)) - ABD(8, 5), отличное от (15), и, возможно, одно или несколько ABD(12,6).

Ладно, я очень рад, что мы до этого сами додумались, как полагается сыщикам; за всякий другой способ я гроша ломаного не дам. ТОМ СОЙЕР (1884) [Марк Твен, Приключения Гекльберри Финна]