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

[halloffame]

Tại một trại hè có $k$ người. Cứ mỗi $m$ người trong trại hè ($m\geq 3$) thì có đúng 1 bạn chung. Quy ước rằng nếu $A$ là bạn $B$ thì $B$ là bạn $A$, và $A$ không là bạn của chính anh ta. Hỏi trại hè có bao nhiêu người?

[phuocdinh1999]

Tại một trại hè có $k$ người. Cứ mỗi $m$ người trong trại hè ($m\geq 3$) thì có đúng 1 bạn chung. Quy ước rằng nếu $A$ là bạn $B$ thì $B$ là bạn $A$, và $A$ không là bạn của chính anh ta. Hỏi trại hè có bao nhiêu người?

Rõ ràng luôn tồn tại 2 người quen nhau là $A_1$ và $A_2$

Với 2 người trên thì tồn tại $A_3$ quen cả hai. (gt)

Với 3 người $A_1,A_2,A_3$ thì tồn tại người A_4 quen cả ba (do $m \geq 3$)

....

Làm liên tục như trên, ta được $m+1$ người $A_1,A_2,.. , A_{m+1}$ đôi một quen nhau.

Giả sử tồn tại B không thuộc nhóm trên 

 

TH1: B có ít nhất 2 người bạn, giả sử $A_1,A_2$ 

Khi đó xét $m$ người $B,A_3,A_4,...,A_{m+1}$ thì $m$ người này có ít nhất 2 bạn chung là $A_1,A_2$ (vô lý)

 

TH2: B có đúng 1 người bạn, giả sử là C

Xét $m$ người $B,C,A_4,A_5,...,A_{m+1}$ thì họ có đúng một người bạn chung là D 

Khi đó B có ít nhất 2 người bạn (mâu thuẫn)

 

Như vậy không tồn tại ai ngoài nhóm $m+1$ người trên. Vậy trại hè có $m+1$ người 

[halloffame]

Xét thiếu TH B không có bạn kìa               

[ducvipdh12]

Tại một trại hè có $k$ người. Cứ mỗi $m$ người trong trại hè ($m\geq 3$) thì có đúng 1 bạn chung. Quy ước rằng nếu $A$ là bạn $B$ thì $B$ là bạn $A$, và $A$ không là bạn của chính anh ta. Hỏi trại hè có bao nhiêu người?

ý tưởng là như thế này:

Nhận xét đầu tiên là mọi học sinh đều có 1 người bạn

Ta giả sử rằng $A_{1},A_{2},...,A_{N}$ là bạn lẫn nhau với $n\in \mathbb{N},2\leq n\leq m$. Khi đó thì sẽ có 1 học sinh $A_{n+1}$ là bạn chung của tất cả học sinh $A_{i}$,$1\leq i\leq n$. Tiếp theo,chúng ta bắt đầu với 1 cặp học sinh,giả sử là $A_{1},A_{2}$ là bạn,và cứ tiếp tục thêm 1 học sinh cho đến khi có chứa $m+1$ học sinh $A_{1},A_{2},...,A_{m+1}$ là bạn lẫn nhau

Tiếp theo ta chứng minh không còn ai ngòai $m+1$ học sinh đó. Khi đó tồn tại 1 học sinh $B$ ở trong trại. Khi đó $B$ phải có 1 bạn.Ta xét các trường hợp sau:

TH 1: Nếu $B$ có ít nhất 2 bạn trong số $A_{1},A_{2},...,A_{m+1}$. Không mất tính tổng quát giả sử đó là $A_{1},A_{2}$. Khi đó $B,A_{3},A_{4},...,A_{m+1}$ có 2 bạn chung.Trái giả thiết

TH 2:Nếu $B$ có nhiều nhất là 1 bạn trong số $A_{1},A_{2},...,A_{m+1}$. Không mất tính tổng quát giả sử rằng $A_{2},A_{3},...,A_{m+1}$ không phải bạn của $B$. Khi đó $B,A_{2},A_{3},...,A_{m+1}$ có 1 bạn chung $C$,$C\neq A_{i};1\leq i\leq m+1$. Khi đó kể từ $m\geq 3$ thì $C$ có 2 bạn chung trong số $A_{1},A_{2},...,A_{m+1}$. Khi đó chứng minh tương tự TH 1

Vậy $k=m+1$