Bài toán hóc búa 'hiệp sĩ và kẻ lừa dối' ở Nga

Trong một kỳ thi Olympic Toán dành cho học sinh lớp 9 có bài toán "hiệp sĩ và kẻ lừa dối" khá thú vị. Bài toán gây nhiều khó khăn ...

Trong một kỳ thi Olympic Toán dành cho học sinh lớp 9 có bài toán "hiệp sĩ và kẻ lừa dối" khá thú vị. Bài toán gây nhiều khó khăn cho những ai lần đầu tiếp cận dạng toán như thế này.

Đề bài toán "Hiệp sĩ và Kẻ lừa dối"


30 người ngồi quanh một bàn tròn 30 chiếc ghế đánh số theo thứ tự từ 1 đến 30. Một số trong họ là hiệp sĩ, một số là kẻ lừa dối. Hiệp sĩ luôn nói thật còn kẻ lừa dối luôn nói dối. Mỗi người có đúng một người bạn trong số những người khác. Hơn nữa, bạn của hiệp sĩ là một kẻ lừa dối và bạn của kẻ lừa dối lại là một hiệp sĩ.
Mỗi người đều được hỏi: "Có phải bạn của anh đang ngồi cạnh anh không?". 15 người ngồi ở vị trí mang số lẻ trả lời: "Đúng".
Tìm số người ngồi ở vị trí mang số chẵn cũng trả lời: "Đúng".
Ảnh minh họa

Lời giải bài toán "Hiệp sĩ và Kẻ lừa dối"


Từ đề bài ta suy ra trong 30 người có đúng 15 cặp hiệp sĩ – kẻ lừa dối là bạn của nhau. Ta có thể dễ dàng đoán được đáp số của bài toán bằng cách “giả định” 15 người ở vị trí lẻ đều là hiệp sĩ. Khi đó, dĩ nhiên bạn của họ đều ngồi cạnh ở các vị trí chẵn và đều là kẻ lừa dối, do đó không có ai nói “Đúng”. Đáp số là 0.

Tuy nhiên, đó chỉ là dự đoán đáp số chứ không phải lời giải. Với cách hỏi ở đề bài, ta biết đáp số là 0. Nhưng để khẳng định điều này, ta phải chứng minh chứ không chỉ là đưa ra một ví dụ như vậy.

Bí quyết của lời giải là ở nhận xét quan trọng sau: Trong 2 người là bạn của nhau, chỉ có đúng 1 người nói “Đúng” cho câu hỏi "Có phải bạn của anh đang ngồi cạnh anh không?".

Thật vậy, nếu có hai người (1 hiệp sĩ và 1 kẻ lừa dối) là bạn của nhau. Xét 2 trường hợp:

1) Nếu họ ngồi cạnh nhau thì hiệp sĩ sẽ nói "Đúng", còn kẻ lừa dối nói “Không”.

2) Nếu họ không ngồi cạnh nhau thì hiệp sĩ nói “Không”, còn kẻ lừa dối nói “Đúng”.

Như vậy, vì ta có 15 cặp bạn nên ta có đúng 15 câu trả lời “Đúng”. Vì cả 15 người ở vị trí mang số lẻ đã nói “Đúng” nên tất cả những người ở vị trí số chẵn đều nói “Không”. Tức là đáp số bằng 0.

Theo Soha. Người đăng: Sơn Phan.
Tên

Ảnh đẹp,18,Bài giảng điện tử,6,Bạn đọc viết,225,Bất đẳng thức,51,Bđt Nesbitt,3,Bổ đề cơ bản,9,Bồi dưỡng học sinh giỏi,29,Cabri 3D,2,Các nhà Toán học,88,Câu đố Toán học,26,Câu đối,3,Cấu trúc đề thi,6,Chỉ số thông minh,4,Chuyên đề Toán,250,Công thức Thể tích,7,Công thức Toán,49,Cười nghiêng ngả,32,Danh bạ website,1,Dạy con,8,Dạy học Toán,91,Dạy học trực tuyến,2,Dựng hình,5,Đạo hàm,3,Đề cương ôn tập,32,Đề kiểm tra 1 tiết,24,Đề thi - đáp án,659,Đề thi Cao đẳng,15,Đề thi Cao học,7,Đề thi Đại học,140,Đề thi học kì,101,Đề thi học sinh giỏi,78,Đề thi THỬ Đại học,264,Đề thi Tốt nghiệp,37,Đề tuyển sinh lớp 10,69,Điểm sàn Đại học,5,Điểm thi - điểm chuẩn,130,Đọc báo giúp bạn,13,Epsilon,6,File word Toán,12,Giải bài tập SGK,16,Giải chi tiết,31,Giải Nobel,1,Giải thưởng FIELDS,23,Giải thưởng Lê Văn Thiêm,1,Giải tích,13,Giải trí Toán học,97,Giáo án điện tử,10,Giáo án Hóa học,2,Giáo án Toán,15,Giáo án Vật Lý,3,Giáo dục,228,Giáo trình - Sách,73,Giới hạn,3,GS Hoàng Tụy,8,GSP,6,Gương sáng,83,Hằng số Toán học,13,Hình gây ảo giác,9,Hình học không gian,68,Hình học phẳng,40,Học bổng - du học,4,Khái niệm Toán học,13,Khảo sát hàm số,23,Kí hiệu Toán học,7,LaTex,10,Lịch sử Toán học,63,Linh tinh,8,Logic,8,Luận văn,1,Luyện thi Đại học,221,Lượng giác,28,Lương giáo viên,3,Ma trận đề thi,7,MathType,7,McMix,2,McMix bản quyền,3,McMix Pro,3,McMix-Pro,3,Microsoft phỏng vấn,11,MTBT Casio,22,Mũ và Logarit,22,MYTS,8,Nghịch lí Toán học,5,Ngô Bảo Châu,46,Nhiều cách giải,28,Những câu chuyện về Toán,10,Olympiad,140,Perelman,8,Ph.D.Dong books,7,Phần mềm Toán,26,Phân phối chương trình,3,Phụ cấp thâm niên,3,Phương trình hàm,4,Sách giáo viên,12,Sách Giấy,5,Sai lầm ở đâu?,10,Sáng kiến kinh nghiệm,6,Số phức,20,Sổ tay Toán học,4,Tạp chí Toán học,29,TestPro Font,1,Thiên tài,61,Thơ - nhạc,9,Thủ thuật BLOG,14,Thuật toán,3,Thư,2,Tích phân,43,Toán 10,89,Toán 11,105,Toán 12,171,Toán 9,28,Toán Cao cấp,24,Toán học Tuổi trẻ,26,Toán học - thực tiễn,71,Toán học Việt Nam,20,Tổ hợp,8,Trắc nghiệm Toán,165,Tuyển dụng,10,Tuyển sinh,193,Tuyển sinh lớp 6,5,Tỷ lệ chọi Đại học,6,Vật Lý,23,Vẻ đẹp Toán học,65,Vũ Hà Văn,2,Xác suất,17,
ltr
item
Toán Học Việt Nam: Bài toán hóc búa 'hiệp sĩ và kẻ lừa dối' ở Nga
Bài toán hóc búa 'hiệp sĩ và kẻ lừa dối' ở Nga
https://1.bp.blogspot.com/-v4nou51mlMA/XeP7gNuT81I/AAAAAAAATYw/OLBItRwk0jw6jykUBD7kHSYrSK9MtmeZwCLcBGAsYHQ/s1600/hiep-si.jpg
https://1.bp.blogspot.com/-v4nou51mlMA/XeP7gNuT81I/AAAAAAAATYw/OLBItRwk0jw6jykUBD7kHSYrSK9MtmeZwCLcBGAsYHQ/s72-c/hiep-si.jpg
Toán Học Việt Nam
https://www.mathvn.com/2019/12/bai-toan-hoc-bua-hiep-si-va-ke-lua-doi.html
https://www.mathvn.com/
https://www.mathvn.com/
https://www.mathvn.com/2019/12/bai-toan-hoc-bua-hiep-si-va-ke-lua-doi.html
true
2320749316864824645
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS CONTENT IS PREMIUM Please share to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy