Распечатать запись Распечатать запись

Одна комбинаторная задача

Интересная комбинаторная задача из книги
László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.

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

1) В каждом клубе может быть только нечетное число членов.
2) Каждые два клуба имеют четное число общих членов.

Какое максимальное число различных клубов может быть создано в этом городе?

Довольно простое и красивое решение этой задачи получается, если воспользоваться методами линейной алгебры.

Перенумеруем жителей города числами от 1 до n. Сопоставим каждому клубу C_1,C_2,\ldots,C_m вектор n-мерного линейного пространства, компоненты которого нули и единицы (вектор инцидентности) следующим образом: j-я компонента вектора V_i равна единице, если j-й житель города принадлежит клубу C_i, и нулю в противном случае.

Рассмотрим скалярное произведение векторов n-мерного пространства X=(x_1,x_2,\ldots,x_n) и Y=(y_1,y_2,\ldots,y_n), определенное стандартным образом:

(X,Y)=x_1y_1+x_2y_2+\ldots+x_ny_n.

Очевидно, что скалярное произведение векторов V_i и V_j равно количеству общих членов клубов C_i и C_j. Теперь правила, по которым создаются клубы, могут быть переформулированы следующим образом:

(V_i,V_j) нечетное число при i=j, четное число при i\ne j.

Можно ввести еще одно упрощение, поскольку мы рассматриваем (0,1)-векторы: рассматривать умножение и сложение над полем вычетов по модулю 2 (т.е. вместо результата арифметических операций записывать остатки от деления этих результатов на 2, так, например 1+1 будет равно 0). Тогда правила образования клубов перепишутся следующим образом:

(V_i,V_j)=\left\{\begin{array}{ll}<br />
1, i=j,\\<br />
0,i\ne j.<br />
\end{array}\right.

Докажем, что при выполнении этих условий векторы V_j должны быть линейно независимы над полем вычетов по модулю 2. В самом деле, рассмотрим их линейную комбинацию, равную нулю

\lambda_1V_1+\lambda_2V_2+\ldots+\lambda_mV_m=0

(здесь \lambda_j\in\{0,1\}). Докажем, что все \lambda_j=0, (j=1,2,\ldots,m). Умножим скалярно обе части приведенного выше равенства на V_1, получим

\lambda_1(V_1,V_1)+\lambda_2(V_1,V_2)+\ldots+\lambda_m(V_1,V_m)=0,

откуда, в соответствии с правилами, \lambda_1=0. Аналогично получаем, что и остальные \lambda_j равны нулю. Следовательно, все векторы V_j линейно независимы, следовательно, m\le n.

Очевидно, что n клубов создать можно, причем сделать это можно разными способами. Так, в каждый клуб может входить ровно один житель города, или, наоборот, в каждый клуб не входит ровно один житель города.

Тем самым задача решена, и максимальное число клубов, которые могут создать жители города при выполнении условий задачи, равно n.

Комментариев: 3

  1. 1 Дмитрий:

    :o Почему нельзя было сделать так?
    Пусть клубов m.
    Очевидно, что n клубов можно открыть(в каждом клубе по 1 члену, кол-во общих членов для двух различных клубов равно 0).
    Получаем, что m >= n.
    Если m > n, то по принципу Дирихле получаем, что в одном из клубов кол-во членов равно 0. Т.к. 0 – четное число, получили противоречие.
    m = n.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Дмитрий, один человек может быть членом нескольких клубов одновременно. Принцип Дирихле тут не работает.

    [Ответить]

  2. 2 Андрей:

    Очень красивое решение.

    [Ответить]

Оставьте свой отзыв

Добавить изображение