Toán vui

ddth · 03-05-2008 08:23 PM

Mọi người thử làm bài này nhé.Mình không có ai quen ở ngân hàng nên không có tiền thưởng,coi như phần thưởng là "relax" thôi nhé

Câu 1:
Có N anh cướp biển sắp bị xử chém. Họ xếp thành một hàng dài. Mỗi người đội một chiếc nón, xanh hoặc đỏ. Cướp biển số 1 chỉ thấy nón (và màu nón) của cướp biển số 2, 3, N; cướp biển số 2 chỉ thấy nón của số 3, 4, N; vân vân. Dĩ nhiên, vì thế mỗi cướp biển không biết màu nón mình đang đội và màu nón của các cướp biển đứng trước mình trong hàng.

Đao phủ bắt đầu chém từng cướp biển một, từ số 1 đến số N. Tuy nhiên, trước khi chém mỗi cướp biển thì đao phủ cho hắn một cơ hội: đoán màu nón của mình. Nếu nói đúng màu nón thì được tha. Tất cả các cướp biển đều nghe thấy nhau trả lời, nhưng không biết ai bị chém ai không.

Trước hôm ra xử bắn, bọn cướp biển họp lại và tìm một thuật toán trả lời để cho tổng số cướp biển bị chém là ít nhất trong trường hợp tệ nhất (in the worst case). Ví dụ: nếu cướp biển số 2k-1 trả lời bằng màu nón của cướp biển 2k, và cướp biển 2k lập lại câu trả lời này, thì tệ nhất cũng chỉ có một nửa số cướp biển bị chém.

Nếu bạn là cướp biển thì bạn thiết kế thuật toán thế nào?

Các bài viết cùng chuyên mục:

ddth · 04-05-2008 02:26 PM

Chán thế,chưa ai có đáp án à

Câu 2 nhé:
Tèo leo lên đỉnh Olympia. Bắt đầu sáng thứ bảy từ chân núi đến tối thì lên đến đỉnh. Ngủ một đêm, sáng chủ nhật Tèo leo xuống, đến hoàng hôn thì đến chân núi. Chứng minh rằng có cùng một thời điểm (ví dụ như 1 giờ 2 phút chiều) trong ngày thứ bảy và chủ nhật mà Tèo ở cùng một độ cao.

Câu 3:
Có n điểm xanh và n điểm đỏ trên mặt phẳng, không có 3 điểm nào thẳng hàng, các điểm đều khác nhau. Chứng minh rằng có một cách ghép cặp 1-1 xanh đỏ sao cho các đoạn thẳng nối các cặp này không cắt nhau.

Ưu tiên những giải thích rõ ràng,dễ hiểu

ddth · 04-05-2008 08:00 PM

Chán nhỉ,đố thế mà không ai làm được.
Chán wa'

**Kunkun** · 06-05-2008 01:04 AM

Trả lời câu 2 trước đã, mấy câu còn lại khó quá (ko bít co đúng ko???)
Vẽ đồ thị của 2 lần trèo ,trục hoành là thời gian , trục tung là độ cao
ta thu được 2 hàm(cùng tập xác định và tập giá trị) : 1 hàm đồng biến ,1 hàm nghịch biến cắt nhau tại 1 điểm , điểm đó chính là thời điểm trong ngày thứ bảy và chủ nhật mà Tèo ở cùng một độ cao.

Đúng chứ

ddth · 06-05-2008 05:33 PM

Câu 2 trả lời thế là đúng rồi,dựa vào tính chất liên tục của hàm số.Kunkun giỏi quá

Nhưng mà giải thích như thế thì các em cấp 2 sao hiểu được.Nói thế này dễ hiểu hơn này.

Giả sử hôm sáng CN Tèo bắt đầu đi từ đỉnh Olympia xuống.Cùng lúc đấy Tí - bạn của Tèo đi từ dưới chân núi lên.Giả sử Tí đi y hệt như Tèo hôm qua (quan hệ chiều cao - thời gian như nhau).Tèo và Tý chắc chắn sẽ phải gặp nhau ở 1 điểm nào đó vào 1 lúc nào đó (giả sử 1h2') .Đó chính là thời điểm mà ngày hôm qua và hôm nay Tèo có cùng độ cao

Câu 4 nhé:
Có n điểm trong đó không có đường thẳng nào chỉ đi qua 2 điểm.Chứng minh n điểm thẳng hàng

**Cesc** · 06-05-2008 05:57 PM

Câu 1:
Đáp án là N-1 người còn sống (chắc chắn) nhé.

Nhưng không biết nói thế nào cho dễ hiểu cả

Ai giúp tớ với

**dj3uB3o** · 06-05-2008 06:37 PM

có thể so sánh việc trả lời câu 4 như việc chứng minh trong một hình tròn có n đướng kính

ddth · 10-05-2008 10:13 AM

Gửi bởi dj3uB3o

có thể so sánh việc trả lời câu 4 như việc chứng minh trong một hình tròn có n đướng kính

Thật là tớ không hiểu ý tưởng của cậu

Gửi bởi Cesc

Câu 1:
Đáp án là N-1 người còn sống (chắc chắn) nhé.

Nhưng không biết nói thế nào cho dễ hiểu cả

Ai giúp tớ với

Ai không giải thì tớ giải vậy.

Tên cướp đầu tiên sẽ đếm số mũ xanh và đỏ của những người đứng sau mình và nói mũ của mình sao cho tổng số mũ đỏ là số chẵn.Các tên cướp từ thứ 2 trở đi sẽ tự suy luận ra màu mũ của mình.

Vì thế chỉ có tên cướp đầu tiên là không đảm bảo về tính mạng thôi.

**lnhoa** · 09-04-2009 01:05 AM

Gửi bởi ddth

Thật là tớ không hiểu ý tưởng của cậu

Ai không giải thì tớ giải vậy.

Tên cướp đầu tiên sẽ đếm số mũ xanh và đỏ của những người đứng sau mình và nói mũ của mình sao cho tổng số mũ đỏ là số chẵn.Các tên cướp từ thứ 2 trở đi sẽ tự suy luận ra màu mũ của mình.

Vì thế chỉ có tên cướp đầu tiên là không đảm bảo về tính mạng thôi.

cái này nghe giống bit chẵn lẻ nhỉ