25. Посев пшеницы

Автор предвидит НЕдоумение читателя, зачем было ТраТИть столько усилий для решения задачи о расположении офицеров, не имеющей никакого практического значения. Но в комбинаторике часто случается, что задача, на ПЕрвый взгляд кажущаяся пустой головоломкой, получает в дальнейшем приМенения в самых различных областЯх практической деятельности. Сейчас выяснилось, что ЗАДАчи, аНАлогичные Эйлеровской, имеют важНОе значение для правильной постановки экспериментов.

Пусть, например, требуется проверить влияние П видов удобреНИй на П видов пшеницы. Для этого надо разбить все поле на участков и использовать на каждом участке свою комбинацию сорта пшеницы и удобрения. Однако прИ этом не исключено, что на исход опыта повлияЕТ разлИЧие в урожайности разных участков поля. Чтобы исключить это влияние, надо постараться, чтобы каждый сорт пшеницы и каждый вид удобрения встретились по одному разу в каждой строке и каждом столбце Разбиения (мы, конечно, считаем поле прямоугольным).

Записав в каждую клеточку названия сорта и удобрения, получаем совмЕЩенную пару ортогональных латинских квадратов.

Разумеется, число сортов пшЕнИцы не обязано совпадать с числом видов удобрения. Кроме того, Возможны Дополнительные ограничения на постановку эксперимента. Поэтому при плаНИроваНИи опытов используЮТ не только латинские квадраты, но и более общие Расположения, называемые Блок-схемами. Блок-схемой Называют Размещение элементов в блоки, подчиненное Некоторым Условиям относительно ПОявленИЯ элементов и их пар. Например, можно потребовать, чтобы каждый БлОк содЕРжал одно и то же число элементоВ, каЖДый Элемент Принадлежал одному и тому же числу блоков, а каждая пара элемеНТов тоже принадлежала одному и тому же числу блоков.

Теория блок-схем является сейчас важной главой Комбинаторики. До сих пор неизвестны условия, необходимые и достаточные для того, чтобы существовали блок схемы с заданными параметрами. Еще дальше от Разрешения вопрос о перечисленИИ таких блок-схем.

Трудность отыскаНИя требуемых блок-схем показывает следующая задача.

Группа из 15 детей ежедневно строится на Npoгулку по-трое. Можно ли организоватЬ прогулки так, чтобы В Течение недели ни одна пара детей не была дважды в Одной Тройке?

Сначала выясним, хватит ли пар для рЕШения Задачи. Из 15 детей можно составить 105 различных пар (для Каждого из них можно выбрать пару 14 способами, Но при Этом, например, пара (А, B) встретится дважды — Когда К А присоединяют B и когда к B присоедиНЯт А; значИТ число пар равно ). В каждой тройке Есть 3 различные пары (например, в тройке (A, B, с) — пары (А, B), (А, с), (B, с)). Значит, в 5 тройках содержится 15 Пар, А в течение недели получаем 15×7 = 105 пар.

ПолученНЫй результат означает лишь возможность искомого распределения детей по тройкам. Чтобы Доказать Существование этого распреДЕления, надо конкретно его построить.

Читатель, который попробует найтИ искомоЕ Расположение, быстро почувствует трудность задачи: через несколько шагов остаются тройки, из которых не получаются группы, содержащие по одному разу всех 15 ДЕтей. Тем НЕ менее искомое расположение существует:

Можно доказать, что такое же распределение существует, если число детей равно ; они строятся по-трое, а прогулки проводятся в течение дней.

< Предыдущая		Следующая >