Trong một cuộc họp có 10 người. CMR: Luôn tìm được 2 người có số người quen trong số dự họp là như nhau (Áp dụng nguyên lý Dirichlet)
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
PU
0
1 tháng 7 2015
Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n–1. Rõ ràng trong phòng không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là 10–1 (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành 10–1 nhóm.
Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau. (đpcm)
22 tháng 4 2017
Học cùng lớp thì phải quen nhau hết nên n người đều quen với n-1 người
22 tháng 4 2017
mình nghĩ làm như thế này:
ta chia n người đó vào n phòng tương ứng từ 0 đến n-1 phòng.
mà n chia n-1=1(dư 1 ) { cho phép chia này tớ nghĩ thế }.vay theo nguyên lí dirichle trong phòng có n người luôn tìm được 2 người có số người quen bằng nhau
TN
8 tháng 11 2018
Bài 1:
Các đại biểu tương ứng với 6 điểm A, B, C, D, E, F. Hai đại biểu X và Y nào đó mà quen nhau thì ta tô đoạn thẳng XY bằng màu xanh còn nếu X vá Y không quen nhau thì tô đoạn XY màu đỏ.
Xét 5 đoạn thẳng AB, AC, AD, AE, AF: Theo nguyên tắc Dirichlet thì tồn tại ba đoạn cùng màu. Giả sử AB, AC, AD màu xanh. Xét ba điểm B, C, D: vì 3 đại biểu nào cũng có hai người quen nhau suy ra một trong ba đoạn BC, CD, DB màu xanh.
Giả sử BC màu xanh thì A, B, C đôi một quen nhau.
Còn nếu AB, AC, AD màu đỏ thì B, C, D đôi một quen nhau.
TN
8 tháng 11 2018
Theo nguyên lý Di-rich-le ta suy ra: Tồn tại hai số trong 20 số khi chia cho 19 có cùng số dư. Suy ra hiệu của hai số đó chia hết cho 19.
Giả sử 10n, 10m là hai số có cùng số dư khi chia cho 19 (1 ≤ n < m ≤ 20).
- 10m – 10n ⋮ 19
- 10n.(10m-n – 1) ⋮ 19, mà 10n không chia hết cho 19 nên suy ra:
10m-n – 1 ⋮ 19
- 10m-n – 1 = 19k (k ∈ N)
- 10m-n = 19k + 1 (đpcm).
31 tháng 7 2016
Người thứ nhất bắt tay 11 người còn lại
Người thứ hai bắt tay 10 người còn lại
Người thứ ba bắt tay 9 người còn lại
........
Người thứ mười một bắt tay người còn lại
Tổng số cái bắt tay có trong cuộc họp là:
(11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) x 2 = 132 (cái bắt tay)
ĐS: 132 cái bắt tay
LD
3 tháng 11 2016
Do trong phòng có 100 người, mỗi người quen it nhất 67 người còn lại nên số người mà người đó không quen nhiều nhất là:
100-67-1= 32( người)
Ta giả sử 1 người bất kỳ trong 100 người đó là A. Nếu ta loại những người mà A không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68 người( trong đó có A).
Ta lại giả sử 1 trong 68 người còn lại trong phòng( khác A) là B. Nếu ta loại đi những người mà B không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68-32=36( người) trong đó có A và B.
............................. 36......................................(khác A,B) là C.............................................C................................................
.....................................36-32=4( người) trong đó có A,B và C.
Trong 4 người còn lại ta giả sử người khác A,B,C là D thì khi đó trong phòng có 4 người: A,B,C và D suy ra A,B,C,D đôi một quen nhau. Do đó tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau( đpcm)
Lời giải:
Trong cuộc họp không thể đồng thời có người quen $0$ người (không quen biết ai cả) và có người quen $9$ người (quen hết). Do đó số người quen của mỗi người trong cuộc họp có thể rơi vào các giá trị $0,1,...,8$ hoặc $1,2,...,9$. Tóm lại, số người quen biết của mỗi người trong cuộc họp có thể là 1 trong 9 giá trị (tương ứng có 9 nhóm)
Theo nguyên lý Dirichlet, tồn tại ít nhất $\left[\frac{10}{9}\right]+1=2$ người có cùng số người quen.