Giáo sư Peter Winkler có một quyển sách về đố vui cực hay. Tôi sẽ trích ra vài câu hỏi trong quyển này ở vài posts tới cho “các câu hỏi phỏng vấn”. Có vài câu hỏi trong chuỗi “các câu hỏi phỏng vấn” có trong sách, nhưng tôi biết chúng qua các nguồn khác. Quyển sách này tôi mới mua hôm qua. Khó mà đặt nó xuống.
- Cô giáo vào lớp học ngày đầu tiên của năm mới, thấy hai chú nhóc trông giống hệt nhau ngồi bàn đầu, tên là Trần văn Tí và Trần văn Tèo.
- “Các em sinh đôi hả“, cô giáo hỏi.
- “Dạ không phải“, Tí và Tèo đồng thanh trả lời.
Cô giáo kiểm tra học bạ thì thấy Tí và Tèo có cùng cha mẹ và được sinh ra cùng ngày. Làm thế nào có thể thế được?
- Cả nước trong tình trạng thiếu xăng. Có một con đường vòng (tròn) rất dài. Các trạm xăng nằm rải rác trên đường. Tèo muốn lái xe hơi một vòng trên đường và quay lại chỗ cũ. Tổng cộng số xăng trên tất cả các trạm cộng lại vừa đủ cho chuyến đi này. Chứng minh rằng, từ một bình xăng rỗng, có một trạm xăng mà nếu Tèo bắt đầu đi từ đó thì sẽ kết thúc được chuyến đi.
- Một hình chữ nhật được phân hoạch thành nhiều hình chữ nhật nhỏ. Mỗi hình chữ nhật nhỏ này hoặc có chiều dài nguyên hoặc có chiều rộng nguyên (hoặc cả hai). Chứng minh rằng hình chữ nhật lớn cũng có tính chất tương tự.
7 Comments
58. 2 anh em có thể sinh cùng ngày nhưng khác năm
59. Nghe thú vị nhưng trong thời gian ngắn em chưa nghĩ ra được
60. Quy nạp theo số hinh chữ nhật con. Vì ta có thể cắt đôi 1 hình cn có tính chất trên thành 2 hình cn cùng tính chất với số mảnh của phân hoạch nhỏ hơn số mảnh ban đầu : kiếm 1 mảnh nằm ở góc, giữ lại cạnh nguyên của nó, cắt dọc theo cạnh còn lại.
Bạn Mudzot: hai anh em đó sinh cùng ngày cùng tháng cùng năm.
58. 2 anh em sinh này sinh ba, sinh bốn,…
Hì, thử làm 59 phát
.
Gọi K(i) là khoảng cách (km) từ trạm thứ i đến trạm thứ i+1. X(i) là số lít xăng bơm được ở trạm thứ i. Để cho dễ, quy ước cứ 1l đi được 1km.
Như vậy, theo gt, Tổng K(i) = tổng X(i).
Trước tiên, chứng minh, tồn tại một trạm, mà từ đó ta có thể đi đến được trạm kế tiếp.
Giả sử, từ tất cả các trạm, ta không thể đi được đến trạm kế tiếp, khi đó K(i) > X(i). Khi đó, tổng K(i) > tổng X(i), trái giả thiết. Vậy, tồn tại một trạm mà từ đó ta có thể đi đến được trạm kế tiếp.
Cứ tiếp tục, khi đến xe đến được một trạm x nào đó, số xăng còn dư là D, thì ta cộng:
X(x)= X(x) + D.
Và lại trở lại bài toán trên với số trạm giảm đi 1.
Anh mudzot nói rõ câu 60 chút được không? Em không hiểu rõ lắm
59. livahim chưa tính đến trường hợp K(i+1) > X(i+1)+ X(i), khi đó dù X(i) >K(i) cũng không thể xuất phát từ chặng (i). Ngoài ra dùng quy nạp không ổn vì phải di chuyển liên tục, không được nhảy chặng.
Đặt Y(i) = X(i)-K(i). Như vậy Y(i) có dấu +,- hoặc =0. Ta sẽ chứng minh tồn tại chặng J thỏa mãn: Y(J), Y(J) + Y(J+1), Y(J) + Y(J+1) + Y(J+2), … đều >=0. (để dễ hình dung, dùng J+1 thay vì (J+1) mod n)
Ta sẽ chia n chặng thành các đoạn kế tiếp nhau như sau:
Đoạn “-” gồm các chặng mang dấu “-”, hoặc bắt đầu từ một chặng mang dấu “+” cho đến khi tổng các chặng
59 qui nạp được đấy.
Nếu các bạn dùng các dấu nhỏ hơn và lớn hơn thì lưu ý cái này.