сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Какое мак­си­маль­ное ко­ли­че­ство под­мно­жеств из 4 эле­мен­тов можно вы­брать во мно­же­стве из 8 эле­мен­тов так, чтобы пе­ре­се­че­ние любых трёх из вы­бран­ных под­мно­жеств со­дер­жа­ло не более од­но­го эле­мен­та?

Спрятать решение

Ре­ше­ние.

При­ведём два раз­лич­ных при­ме­ра вы­бо­ра вось­ми 4-⁠х эле­мент­ных под­мно­жеств во мно­же­стве X из вось­ми эле­мен­тов, удо­вле­тво­ря­ю­щих усло­вию за­да­чи. Оба при­ме­ра стро­ят­ся, как гео­мет­ри­че­ские объ­ек­ты.

При­мер 1. Будем счи­тать эле­мен­ты X вер­ши­на­ми еди­нич­но­го куба, шесть из вы­бран­ных мно­жеств будут гра­ня­ми этого куба, а остав­ши­е­ся два вер­ши­на­ми двух впи­сан­ных в этот куб пра­виль­ных тет­ра­эд­ров с реб­ром  ко­рень из: на­ча­ло ар­гу­мен­та: 2 конец ар­гу­мен­та . Ни­ка­кие две вер­ши­ны этих тет­ра­эд­ров не лежат на одном ребре куба. Если среди любых трёх из вы­бран­ных под­мно­жеств со­дер­жат­ся оба тет­ра­эд­ра, либо две па­рал­лель­ных грани, пе­ре­се­че­ние пусто. Если это две смеж­ных грани и тет­ра­эдр, то пе­ре­се­че­ние гра­ней даст ребро, ко­то­рое пе­ре­се­ка­ет­ся с тет­ра­эд­ром ровно по одной вер­ши­не. Если это три по­пар­но смеж­ных грани, то их пе­ре­се­че­ние со­дер­жит един­ствен­ную вер­ши­ну вер­ши­ну трёхгран­но­го угла, об­ра­зу­е­мо­го этими гра­ня­ми.

При­мер 2. Будем счи­тать эле­мен­ты X вер­ши­на­ми пра­виль­но­го вось­ми­уголь­ни­ка. За­ну­ме­ру­ем его вер­ши­ны по ча­со­вой стрел­ке от 1 до 8, от­ме­тим четырёхуголь­ник M c вер­ши­на­ми под но­ме­ра­ми 1, 2, 3, 5. Вы­бран­ны­ми под­мно­же­ства­ми будем счи­тать M и ещё семь четырёхуголь­ни­ков, по­лу­ча­е­мых из M по­во­ро­та­ми на углы  дробь: чис­ли­тель: 2 Пи k, зна­ме­на­тель: 8 конец дроби , k = 1, 2, \ldots, 6, 7. Если бы пе­ре­се­че­ние каких-то трёх из них со­дер­жа­ло не мень­ше двух вер­шин, то есть не­ко­то­рую сто­ро­ну или диа­го­наль вось­ми­уголь­ни­ка, от­лич­ную от глав­ных, то, по­вер­нув все эти три четырёхуголь­ни­ка об­рат­но до сов­ме­ще­ния с M, по­лу­чим три раз­лич­ных от­рез­ка оди­на­ко­вой длины, со­еди­ня­ю­щие вер­ши­ны М. По­след­нее не­воз­мож­но, по­то­му, что длины сто­рон и диа­го­на­лей M, из­ме­рен­ных в сто­ро­нах, равны 1, 1, 2, 2, 3, 4, среди них не более двух рав­ных. Если речь идёт о глав­ной диа­го­на­ли длины 4, то оче­вид­но, что она со­дер­жит­ся толь­ко в двух из вось­ми рас­смат­ри­ва­е­мых четырёхуголь­ни­ках.

До­ка­жем, что, если в 8-⁠ми эле­мент­ном мно­же­стве X про­из­воль­но вы­бра­ны де­вять 4-⁠х эле­мент­ных под­мно­жеств, то пе­ре­се­че­ние не­ко­то­рых трёх из них со­дер­жит боль­ше од­но­го эле­мен­та. Сумма мощ­но­стей вы­бран­ных под­мно­жеств равна 36, по­это­му один из эле­мен­тов X, обо­зна­чим его за x, со­дер­жит­ся не менее, чем в k боль­ше или равно 5 из них. Уда­лим из этих k под­мно­жеств x и рас­смот­рим k боль­ше или равно 5 по­лу­чен­ных 3-⁠ёх эле­мент­ных под­мно­жеств в 7-⁠эле­мент­ном мно­же­стве Y, рав­ном X без x. Сумма мощ­но­стей по­лу­чен­ных мно­жеств боль­ше, либо равна 15, по­это­му один из эле­мен­тов Y, обо­зна­чим его за y, со­дер­жит­ся не менее, чем в трёх из k по­лу­чен­ных 3-⁠ёх эле­мент­ных мно­жеств. Сле­до­ва­тель­но, пара эле­мен­тов \boldsymbolx и y со­дер­жит­ся не менее, чем в трёх из де­вя­ти вы­бран­ных 4-⁠х эле­мент­ных под­мно­жеств из X.

 

Ответ: во­семь.

Спрятать критерии
Критерии проверки:

При­мер для вось­ми под­мно­жеств: 3 балла.

До­ка­за­тель­ство оцен­ки: 4 балла.

От­сут­ствие обос­но­ва­ния при­ме­ра: минус 1 балл.