НОМ '20-Областен кръг,12 клас

[poankare56]

Нека S = {1,2,...,2020}, тоест множеството от цели числа от 1 до 2020. За подмножества A и B на S казваме, че A свързва B, ако A съдържа както елемент от B, така и елемент, който не е от B. Колко най-много непразни различни подмножества на S могат да бъдат избрани, така че: за всеки три от избраните подмножества A,B и C, ако A свързва B и B свързва C, то A и C нямат общ елемент?

[drago]

Само изглежда леко страшна с тази терминология. Всъщност не е. Ако си представим (говоря леко през къра) това "свързване" като леко отместване на множеството виждаме, че ако два пъти направим това "отместваме трябва да излезем извън първоначалното множество, т.е. ако $A,B,C$ са свързани в този ред, то $A\cap C=\emptyset$. Това някак ни навежда на миссълта, че не е възможно три множества да имат непразно сечение. Проверява лесно, ако допуснем противното. Това е почти всичко.

[poankare56]

Да, това беше и първото нещо, което още на самата олимпиада се опитах да покажа с конкретни числа, напр. A={1,2,3},B={3,4,5},C={5,6,7} и наистина А И С нямат общ елемент. Това означава ли, че всички такива множества мога да избера като от всичките 2019 елемента избирам 2, след това още 2(като един може да съвпадне с вече избран, за да са множествата свързани) и т.н.? Също двуелементни ли трябва да са множествата,за да е техният брой максимален, или не е задължит.?

[drago]

Това означава, че три множества не могат да имат общ елемент (трябва формално да се докаже). Това означава много. Просто казано всеки елемент на $S$ принадлежи най-много на две множества. От тук например веднага следва, че множествата не могат да бъдат повече от $2\cdot 2020$. Но това няма как да се случи, като се замисли малко човек. Оценката е по-ниска. Иска се още един напън.

[poankare56]

Добре, благодаря, ще се опитам да доразвия тази идея, макар че то това си е отговорът.