Skärande familj

Jag har fastnat på det här problemet.

Jag försöker tänka mig en klocka med n punkter, där man placerar ut n stycken intervall A_s där varje intervall täcker k punkter.

Alla A_f i familjen måste skära med alla andra A_f och varje par av A_f har en unik skärning. Jag blir dock förvirrad när jag tänker på dessa unika skärningar. En specifik mängd tänker jag kan överlappas på 2(k-1) sätt (de k-1 första eller sista elementen).

Antar att $k<n/2$ ?

Observera att $A_s$ och $A_{s+k}$ är disjunkta. Så om t.ex. $A_0\in F$ så måste $-(k-1)\leq s \leq k-1$ för alla $A_s\in F$ . Det ger oss $2(k-1)$ möjliga $k$ -delmängder i $F$ , utöver $A_0$ .

Visa spoiler

Vi kan lista de $2(k-1)$ andra delmängderna i par:

$A_{-(k-1)},A_1$ ;

$A_{-(k-2)},A_2$ ;

...

$A_{-1},A_{k-1}$ .

Notera att var och en av dessa $(k-1)$ par har tomt snitt sinsemellan. Du kan därför som mest välja en mängd ur varje par, vilket tillsammans med $A_0$ ger en övre gräns på $k$ st mängder.

Tack för svaret! Det fanns ingen premiss om att k < n/2, men om man utgår från det så är jag med på hur det går ihop :)

Svara