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

Интересная комбинаторная задача из книги
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} 1, i=j,\\ 0,i\ne j. \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 Андрей:

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

    [Ответить]

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

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