Sau khi học hết lớp 9, 40 học sinh của lớp được tốt nghiệp và mỗi học sinh đã chọn một ngôi trường và ở những địa chỉ khác nhau. Biết rằng mỗi học sinh đều biết số điện thoại của ít nhất 20 bạn và nếu A biết số điện thoại của B thì B cũng biết số điện thoại của A. Chứng minh rằng bất cứ 2 học sinh nào trong lớp cũng có thể liên lạc với nhau bằng điện thoại.
Thử suy luận coi nào
Sau khi học hết lớp 9, 40 học sinh của lớp được tốt nghiệp và mỗi học sinh đã chọn...
Bắt đầu bởi N H Tu prince, 17-05-2012 - 11:10
#2
Đã gửi 17-05-2012 - 13:52
perfectstrong
-
- Quản lý Toán Ứng dụng
-
- 5018 Bài viết
$LOVE(x)|_{x =\alpha}^\Omega=+\infty$
Lời giải:
Gọi 40 điểm $A_1;A_2;...;A_{40}$ trên mặt phẳng đại diện tương ứng cho 40 bạn trong lớp đó. 2 bạn biết số điện thoại nhau, ta nối 2 điểm đó bằng 1 đoạn thẳng.
Do gt nên $\deg A_i\geq 20$. Ta cần chứng minh 2 điểm bất kì sẽ được nối với nhau bằng 1 đường đi.
Giả sử tồn tại $i\neq j$ sao cho $A_i$ và $A_j$ không thể nối với nhau bằng 1 đường đi. (*)
Không mất tính tổng quát, gọi đó là điểm $A_1$ và $A_2$. Nếu không, ta chỉ cần đổi tên các điểm.
Gọi $A_{i_1};A_{i_2};...;A_{i_{20}}$ là các điểm mà $A_1$ nối đến. Do (*) nên không thể tồn tại đường đi giữa $A_2$ và $A_{i_1};A_{i_2};...;A_{i_{20}}$.
Khi đó $\deg A_2 \leq 40-1-20=19$: trái gt đề cho là $\deg A_i \geq 20,\forall i$.
Vậy ta có đpcm.
Gọi 40 điểm $A_1;A_2;...;A_{40}$ trên mặt phẳng đại diện tương ứng cho 40 bạn trong lớp đó. 2 bạn biết số điện thoại nhau, ta nối 2 điểm đó bằng 1 đoạn thẳng.
Do gt nên $\deg A_i\geq 20$. Ta cần chứng minh 2 điểm bất kì sẽ được nối với nhau bằng 1 đường đi.
Giả sử tồn tại $i\neq j$ sao cho $A_i$ và $A_j$ không thể nối với nhau bằng 1 đường đi. (*)
Không mất tính tổng quát, gọi đó là điểm $A_1$ và $A_2$. Nếu không, ta chỉ cần đổi tên các điểm.
Gọi $A_{i_1};A_{i_2};...;A_{i_{20}}$ là các điểm mà $A_1$ nối đến. Do (*) nên không thể tồn tại đường đi giữa $A_2$ và $A_{i_1};A_{i_2};...;A_{i_{20}}$.
Khi đó $\deg A_2 \leq 40-1-20=19$: trái gt đề cho là $\deg A_i \geq 20,\forall i$.
Vậy ta có đpcm.
- Dung Dang Do và ducthinh26032011 thích
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! 
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
