Các câu hỏi phỏng vấn [29]
Ngô Quang Hưng | 17 tháng 07, 2007 | 
Bản để in
Đề tài hôm nay là các số trên vòng tròn.
- 25 hòn sỏi đen và 25 hòn sỏi trắng được xếp thành vòng tròn. Chứng minh rằng có một hòn sỏi mà hai hòn hai bên (trái, phải) đều trắng.
- Có n số thực nằm trên một vòng tròn với tổng không âm. Chứng minh rằng tồn tại một trong n số này, tạm gọi là số x, thỏa mãn điều kiện sau đây: với mọi k > 0 thì tổng của k số thực, kể từ x theo chiều kim đồng hồ, là không âm.
- Giả sử ta có n số nguyên trên một vòng tròn. Ta được phép làm một phép biến đổi, gọi là “biến đổi tếu“, như sau: tìm 3 số (a,b,c) nằm kề nhau liên tục trên vòng tròn, trong đó b < 0, và đổi chúng thành (a+b, -b, c+b). Mệnh đề sau đây đúng hay sai: có thể gán n số nguyên vào một vòng tròn để ta có thể biến đổi tếu mãi mãi, không bao giờ bị kẹt
80. Em nghĩ thế này: 25 hòn sỏi trắng xếp vòng tròn sẽ tạo ra 25 khe để sếp các hòn sỏi đen vào đó. Để không có hòn sỏi nào mà hai hòn kề nó đều trắng thì: không có hai khe nào liền nhau bị bỏ trống, và các khe có sỏi đen phải có không ít hơn 2 hòn sỏi đen. Số khe phải có sỏi đen là 25/2+1=13 khe. Do 13*2=16>25. Nên điều kiện để không có hòn sỏi nào có hai hòn kề nhau là trắng là không thể. Suy ra điều ngược lại là đúng.
Neu em nho ko nham thi 2 cau 81 va 82 anh Hung deu da do trong blog nay roi, chi la duoi dang khac thoi.
@Trang2: cũng có thể. Bây giờ tôi chỉ dùng bộ nhớ 10KB (trong đầu) chứ không kiểm tra lại xem 80 câu trước có trùng hay không. Tôi nghĩ là không trùng lặp, nhưng cũng không đảm bảo 100% được.
Nhìn ngon quá nhưng mà đắt dã man, lần nào cũng đi qua ngó 1 cái chơi thôi, đụng vào thì híc…
Có vẻ các câu hỏi này đã được trả lời gọn gẽ trên http://www.vnqf.org/forums/riddles_and_interview_questions/702-cac_so_tren_vong_tron.html
Cho em xin phép post mấy câu toán đố chưa trả lời của anh Hưng lên trên đấy nhé?
Ừ, dongta cứ post lại, ghi lại nguồn blog KHMT là được.
->80 : Phan chung , gia su ko co vien bi nao co tinh chat nhu tren (hai vien bi canh no deu la trang)
) thi vi tri do la bi trang .Suy ra vi tri i=48 (chia het cho 4) la bi trang => Vo ly .Vay ton tai bi co tinh chat tren
Dat goc i=0 tai 1 vien bi trang bat ki , nhan thay rang khi i tang len i chia 4 du 2 thi vi tri do la bi den , i chia 4 du 0 (chia het
Sư phụ nào giải giúp em bài này với.Thầy em đố mà nghĩ hoài ko ra:
trong 1 thành phố đang có bệnh dịch . thành phố có 10^5 người
biết 1% dân số bị nhiễm bệnh
có 1 trung tâm xét nghiệm.Mỗi ngày trung tâm xét nghiệm tối đa 10^3 mẫu xét nghiệm
(mỗi mẫu xét nghiệm này có thể của >=1 người )
nếu trong 1 mẫu cỡ m bất kì ( m>=1) mà có nhiều hơn 1 người nhiễm bệnh thì kết quả xét nghiệm sẽ sai.
ví dụ: mẫu xét nghiệm cỡ 4 ( người 1, người 2, người 3, người 4) mà người 2 và người 4 nhiễm thì nó sẽ cho kết quả sai
tìm phương án xét nghiệm và số ngày xét nghiệm ít nhất để tìm ra toàn bộ người nhiễm bệnh?
nghe thầy nói là dù dân số có tiến đến vô cực thì kết quả cũng vậy, tức là kết quả ko phụ thuộc số dân.Trong bài này cho 10^5 cho dễ
80. Em xét các bộ ba (x,y,z) (x,y,z thuộc tập {trắng, đen}) theo chiều kim đồng hồ để chỉ màu của bộ 3 bi liên tiếp nhau thuộc vòng tròn. Có tất cả 50 bộ như vậy.
1 bộ ba (x,y,z) được gọi là trắng phải nếu z trắng. Số bộ như thế này là 25.
1 bộ ba (x,y,z) được gọi là trắng trái nếu x trắng. Số bộ như thế này là 25.
Bài toán tương đương với việc chứng minh tồn tại 1 bộ ba vừa trắng phải vừa trắng trái.
Ta giả sử kết luận của bài toán là sai.
Nếu có 1 bộ không trắng phải và không trắng trái, ta có ngay mâu thuẫn bằng nguyên lí Dirichlet.
Nếu 1 bộ luôn hoặc trắng phải, hoặc trắng trái, ta suy ra không tồn tại các bộ có dạng (đen, trắng, đen) và (đen, đen, đen). (*)
Định nghĩa: 1 chùm là tập hợp các bi cùng màu liên tiếp nhau có độ dài (số phần tử) lớn nhất có thể, màu của chùm là màu của các bi đó.
Theo nhận xét (*), ta suy ra các chùm màu trắng luôn có độ dài không ít hơn 2. Mặt khác nếu có 1 chùm có độ dài lớn hơn 2 thì ta có ngay kết luận bài toán là đúng. Vậy các chùm trắng luôn bằng 2 suy ra số bi trắng là chẵn. (mâu thuẫn)
*Ngoài lề: Giáo sư Hưng ơi! Em là học sinh du học mới qua mĩ học undergraduate, 1st semester, chuyên ngành CS. Em có 1 số thắc mắc về cách học, có thể trao đổi với giáo sư qua mail được không ạ?
Bài 82 em thấy hơi giống 1 bài IMO năm nào đó?
Chắc là không tồn tại và cách chứng minh là xét 1 thuần biến nào đó?
81. Gọi P(n) là mệnh đề được phát biểu bởi bài toán.
Ta chứng minh bằng qui nạp P(n) đúng.
P(1), P(2) đúng
Giả sử P(n) đã đúng, ta chứng minh P(n+1) đúng.
Gọi n+1 số thực trên vòng tròn theo thứ tự chiều kim đồng hồ là a[1], a[2]… a[n+1]. (Ta qui ước a[n+1+i]:=a[i] với i thuộc {1,…n+1})
Gọi k là chỉ số thỏa mãn a[k]>=0. Mệnh đề P[n] đúng cho dãy (a[1], a[2]…a[k-1], a[k]+a[k+1], a[k+2]..a[n+1]) (a[1] và a[n+1] có thể không tồn tại) tức tồn tại h sao cho:
a[h]>=0
a[h]+a[h+1]>=0
…
a[h]+….+a[k-1]>=0
và a[h]+…+a[k]>=0 (vì a[k]>=0)
a[h]+….+a[k]+a[k+1]>=0
a[h]+…+a[h+n]>=0
Vậy P[n+1] đúng. Ta có đpcm.