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 As och As+k är disjunkta. Så om t.ex. A0∈F så måste -(k-1)≤s≤k-1 för alla As∈F. Det ger oss 2(k-1) möjliga k-delmängder i F, utöver A0.
Visa spoiler
Vi kan lista de 2(k-1) andra delmängderna i par:
A-(k-1),A1;
A-(k-2),A2;
...
A-1,Ak-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 A0 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 :)
