Problemele etapelor
Articolele din Problemele etapelor
Ediția a IV-a - Problema etapei 1
Data: 1 octombrie 2012 | 3 comentarii
Problema Etapei este în general o problemă cu grad înalt de dificultate, dar tipică și exemplară, fără a cere tehnici speciale de rezolvare, și deci abordabilă indiferent de cunoștințele posedate. Problema Etapei nu este neapărat originală, dar nu este larg cunoscută. Propuneri bine cântărite pentru viitoare Probleme ale Etapei sunt binevenite (prin intermediul resursei Forum). Soluțiile remarcabile pot fi selecționate de către administrator pentru a fi prezentate împreună cu soluția oficială (credite de rigoare către autori).
Un Plan Finit Afin
Fie F o familie de submulțimi distincte ale mulțimii {1, 2, ..., n2}, având proprietatea că fiecare submulțime din F are exact n elemente, iar intersecția a oricare două submulțimi diferite din F are cel mult 1 element. Demonstrați că F are cel mult n2 + n elemente, și dați un astfel de exemplu cu |F| = 12 pentru n = 3.
3 comentarii:
În total avem n^2(n^2-1)/2 astfel de perechi. Fie k numărul de submulțimi din familie.
Datorită ipotezei o pereche {a,b} poate face parte din maxim o submulțime a familiei.
Prin urmare avem în familie maxim kn(n-1)/2 perechi.
Concluzia reiese imediat din inegalitatea evidentă kn(n-1)/2 <= n^2(n^2-1)/2.