Đề thi tin học trẻ không chuyên

Bài 1. Trò chơi cùng nhau qua cầu.
Bốn người cần đi qua một chiếc cầu. Do cầu yếu nên mỗi lần đi không quá hai người, và vì trời tối nên phải cầm đèn mới đi được. Bốn người đi nhanh chậm khác nhau, qua cầu với thời gian tương ứng là 10 phút, 5 phút, 2 phút và 1 phút. Vì chỉ có một chiếc đèn nên mỗi lần qua cầu phải có người mang đèn trở về cho những người kế tiếp. Khi hai người đi cùng nhau thì qua cầu với thời gian của người đi chậm hơn. Ví dụ sau đây là một cách đi:
- Người 10 phút đi với người 5 phút qua cầu, mất 10 phút.
- Người 5 phút cầm đèn quay về, mất 5 phút.
- Người 5 phút đi với người 2 phút qua cầu, mất 5 phút.
- Người 2 phút cầm đèn quay về, mất 2 phút.
- Người 2 phút đi với người 1 phút qua cầu, mất 2 phút.
Thời gian tổng cộng là 10+5+5+2+2 = 24 phút.
Em hãy tìm cách đi khác với tổng thời gian càng ít càng tốt, và nếu dưới 19 phút thì thật tuyệt vời! Lời giải ghi trong tệp văn bản có tên là P1.DOC
HƯỚNG DẪN - LỜI GIẢI - ĐÁP SỐ: 17 phút. Cách đi như sau:
Lượt 1: 2 + 1 sang, 1 quay về thời gian: 3 phút
Lượt 2: 10 + 5 sang, 2 quay về thời gian: 12 phút
Lượt 3: 2 + 1 sang thời gian: 2 phút
Tổng thời gian: 17 phút
===========
Bài 2. Trò chơi bốc sỏi.
Trên mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước đi của mình ra sao?
HƯỚNG DẪN - LỜI GIẢI - ĐÁP SỐ:
Huy sẽ là người thắng cuộc. Thật vậy số sỏi ban đầu là 101 là một số có dạng 5k+1, nghĩa là số nếu chia 5 sẽ còn dư 1. Hoàng phải bốc trước, do số sỏi của Hoàng phải lấy là từ 1 đến 4 do đó sau lượt đi đầu tiên, số sỏi còn lại sẽ lớn hơn 96. Huy sẽ bốc tiếp theo sao cho số sỏi còn lại phải là 96, nghĩa là số dạng 5k+1. Tương tự như vậy, Huy luôn luôn chủ động được để sau lần bốc của mình số sỏi còn lại là 5k+1. Lần cuối cùng số sỏi còn lại chỉ là 1 và Hoàng bắt buộc phải bốc viên cuối cùng và ... thua.
Bài toán tổng quát: có thể cho số viên bi là 5k+1 viên.




Bài 3. Cân táo.
Mẹ đi chợ về mua cho Nga 27 quả táo giống hệt nhau về kích thước và khối lượng. Tuy nhiên người bán hàng nói rằng trong số các quả táo trên có đúng một quả có khối lượng nhẹ hơn. Em hãy dùng một chiếc cân bàn hai bên để tìm ra quả táo nhẹ đó. Yêu cầu số lần cân là nhỏ nhất.
Các em hãy giúp bạn Nga tìm ra quả táo nhẹ đó đi. Nếu các em tìm ra quả táo đó sau ít hơn 5 lần cân thì đã là tốt lắm rồi.

HƯỚNG DẪN - LỜI GIẢI - ĐÁP SỐ:
Số lần cân ít nhất là 3. Cách cân như sau:
Lần 1: Chia 27 quả táo thành 3 phần, mỗi phần 9 quả. Đặt 2 phần lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ nằm ở phần chưa cân, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau lần cân thứ nhất, ta chọn ra được 9 quả táo trong đó có quả táo nhẹ.
Lần 2: Chia 9 quả táo, chọn được ra thành 3 phần, mỗi phần 3 quả. Đặt 2 phần lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ nằm ở phần chưa cân, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau lần cân thứ 2, ta chọn ra được 3 quả táo trong đó có quả táo nhẹ.
Lần 3: Lấy 2 trong số 3 quả táo chọn đặt lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ là quả táo còn lại, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau ba lần cân ta chọn ra được quả táo nhẹ.
===========
Bài 4. Bốc diêm.
Trên bàn có 3 dãy que diêm, số lượng que diêm của