Здравствуйте, Аноним, Вы писали:

А>Видимо очень сложная задачка...
А>Раз никто не смог за это время найти хотя-бы какое-нибудь приемлемое решение...

Хммм. Вот какая идея: рассмотрим целевую матрицу инцедентности (какие элементы с какими соединены), размером N*(N-1).
Каждый раз мы частично покрываем её реальными матрицами K*(K-1), в количестве M штук.

  1 2 3 4 5 6
1 \ a a
2 a \ a
3 a a \
4       \ b b
5       b \ b
6       b b \

a = {1,2,3}
b = {4,5,6}


  1 2 3 4 5 6
1 \     c c
2   \ d     d
3   d \     d
4 c     \ c
5 c     c \
6   d d     \

c = {1,4,5}
d = {2,3,6}

Общая площадь одного покрытия S = M*K*(K-1) = N*(K-1).
Внутри одного покрытия эти матрицы не пересекаются, поскольку мы разбиваем множество на непересекающиеся части. Поэтому S =, а не <=
А вот покрытия между собой могут пересекаться.

Отсюда L >= ]N*(N-1)/S[ = ]N*(N-1)/(N*(K-1))[
L >= ](N-1)/(K-1)[
Это — оценка снизу.

L(6, 2 по 3) >= (6-1)/(3-1) = 5/2 = 2.5
L >= 3