Chủ đề này có 1 trả lời

[bachhammer]

Trong một đêm dạ hội có 2013 người: Một số người trong họ ko quen bít nhau, đồng thời cứ mỗi cặp 2 người ko quen nhau lại có đúng 2 người quen chung, còn hai người quen nhau lại ko có người quen chung. Chứng minh rằng mỗi một người trong dạ hội có một số như nhau những người quen.

[Ispectorgadget]

Trong một đêm dạ hội có 2013 người: Một số người trong họ ko quen bít nhau, đồng thời cứ mỗi cặp 2 người ko quen nhau lại có đúng 2 người quen chung, còn hai người quen nhau lại ko có người quen chung. Chứng minh rằng mỗi một người trong dạ hội có một số như nhau những người quen.

Giả sử $a$ quen $b$ và $A,B$ là tập nhưng người quen của $a,b$. (không kể $a,b$).

Dễ thấy mỗi người trong $A$ quen với duy nhất một người trong $B$ .

Tương tự mỗi người thuộc $B$ cũng quen với duy nhất một người trong $A$.

 

Vậy tồn tại một song ánh đi từ $A\to B$, tức $a$ và $b$ có sô người quen bằng nhau.

 

Nếu $a$ không quen $b$ thì tồn tại $c$ quen chả $a,b$. Do đó số người quen của a và $b$ bằng nhau do cùng bằng số người quen của $c$.