Problemele etapelor

Ediția a IV-a - Problema etapei 2

Data: 12 noiembrie 2012 | 2 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ântarite pentru viitoare Probleme ale Etapei sunt binevenite (prin intermediul resursei Forum). Soluțiile remarcabile pot selecționate de către administrator pentru a prezentate împreună cu soluția oficială (credite de rigoare către autori).

Fie $A$ o mulţime cu $|A|=n\geq 2$ elemente şi fie $\mathcal{F}$ o familie de submulţimi distincte ale lui $A$ , având următoarele două proprietăţi

$|B|\geq 2$ pentru orice $B\in \mathcal{F}$ ;
dacă $|B\cap B^{'}|\geq 2$ pentru $B,\ B^{'}\in \mathcal{F}, \ B\neq B^{'}$ , atunci $|B|\neq |B^{'}|$

Arătaţi că numărul submuţimilor din $\mathcal{F}$ este de cel mult $(n-1)^2$ .

Autentifică-te pe site pentru a putea lăsa un comentariu.

2 comentarii:

Tarkan Yagmuroglu - 12 ianuarie 2013

Problema este o generalizare a problemei de la etapa precedentă.
Mai întâi să vedem câte submulțimi de cardinal m pot face parte din familie. Fie k_m nr. maxim al acestora.
Vom face din nou dublă după perechile {a,b} din AxA. Avem în total n(n-1)/2 perechi.
Dar condiția din ipoteză presupune că o pereche {a,b} face parte din maxim o astfel de submulțime.
Deducem inegalitatea k_m m(m-1)/2 =< n(n-1)/2 de unde k_m =< n(n-1)/m(m-1).
Făcând suma de la m=2 la m=n obținem k_total =< n(n-1) [1- 1/n] = (n-1)^2
bianca musoiu - 5 ianuarie 2013

e cam grea