Đề bài 1( Bài toán trong đề thi Olympic Balkan dành cho học sinh lớp 7-8.)
Cho các số nguyên dương được sắp xếp thành một bảng như hình sau:
Hỏi số 2002 nằm ở cột và hàng thứ bao nhiêu trong bảng trên?
Đáp án: Số 2002 nằm ở cột 49 và hàng 15.
Gợi ý cách giải:
Xét bảng trên theo hàng chéo như hình dưới đây:
Ta thấy các số đầu tiên của mỗi hàng chéo hơn tổng lượng số xuất hiện ở các hàng chéo trước đó một đơn vị. (Ví dụ hai hàng chéo đầu tiên có tổng cộng ba số thì số đầu tiên của hàng chéo thứ ba là số 4).
Xét hàng chéo thứ n có số đầu tiên là x. Tổng lượng số của n - 1 hàng chéo bên trên hàng thứ n bằng 1 + 2 + 3 + ... + (n-1) = (n-1)(n-1 + 1)/2 = n(n-1)/2.
Theo nhận xét đầu tiên ta có số x của hàng thứ n là x = n(n-1)/2 + 1.
Để biết số 2002 ở hàng chéo nào, ta cần tìm n thỏa mãn điều kiện
x = n(n-1)/2 + 1 phải lớn nhất, đồng thời số này phải nhỏ hơn hoặc bằng 2002.
Với x ≤ 2002 hay n(n-1)/2 + 1 ≤ 2002, suy ra n(n-1) ≤ 4002.
Dễ dàng tìm được 62 và 63 là cặp số tự nhiên liên tiếp lớn nhất có tích nhỏ hơn 4002.
Suy ra n = 63 hay số 2002 nằm ở hàng chéo 63.
Số đầu tiên của hàng chéo 63 bằng 63.62/2 + 1 = 1954. Vì số 1954 là số đầu tiên của một hàng chéo và cũng là số đầu tiên của một hàng ngang. Suy ra số 1954 cũng là số đầu tiên của hàng ngang thứ 63.
Số 2002 hơn số 1954 là 48 đơn vị. Suy ra số 2002 nằm ở hàng ngang thứ
63 - 48 = 15.
Số 1954 nằm ở cột đầu tiên. Suy ra số 2002 nằm ở cột thứ 1 + 48 = 49.
Kết luận: Số 2002 nằm ở cột 49, hàng 15 trong bảng đã cho.
===========================================================================================================
Đề bài 2: (của thầy Trần Nam Dũng)
Có n người bị tình nghi một vụ ăn cắp tài khoản ngân hàng. Những người này chỉ là kỹ sư tin học hoặc nhà quản lý.
Tuy nhiên, hồ sơ của họ đều đã bị hủy và không ai biết ai là ai, do vậy cảnh sát cần thẩm vấn từng người.
Điều tra ban đầu cho thấy chắc chắn hung thủ là người quản lý.
Biết rằng các kỹ sư tin học luôn luôn nói thật còn các nhà quản lý thì không chắc như vậy. Và hơn nữa, n người này đều biết nghề nghiệp thật sự của nhau.
Cảnh sát cần đặt câu hỏi để xác định ai làm nghề gì và câu hỏi chỉ có thể ở dạng trả lời có hoặc không, đúng hoặc sai …
1. Nếu như số kỹ sư tin học nhiều hơn số nhà quản lý (trong n người), phải hỏi ít nhất bao nhiêu câu để tìm ra ít nhất một kỹ sư tin học?
2. Nếu số kỹ sư ít hơn số nhà quản lý, liệu có thể tìm ra hung thủ?
Giải:
Đáp án câu 1. Với n lẻ, cần n-2 câu hỏi và với n chẵn, cần n-3 câu hỏi.
Chúng tôi gợi ý một chiến thuật như sau: chia hàng người thành 3 hàng: hàng nghi vấn, hàng khả tin, và hàng bị loại. Bắt đầu chọn ngẫu nhiên 1 người cho vào hàng “khả tin” và tất cả những người còn lại cho vào hàng “nghi vấn”.
Tiến hành hỏi như sau: chọn một người X trong hàng “nghi vấn” và một người Y ở đầu hàng “khả tin” và hỏi Y: “X là nhà quản lý hay kỹ sư tin học?” (hoặc “X có phải là nhà quản lý?” …).
+ Nếu câu trả lời là “quản lý”, cho cả X lẫn Y vào hàng “bị loại”.
+ Nếu câu trả lời là “kỹ sư”, cho X vào đầu hàng “khả tin”.
+ Nếu hàng “khả tin” không còn ai, chọn ngẫu nhiên một người ở hàng “nghi vấn” cho vào hàng “khả tin”.
Tiến hành hỏi như trên cho đến khi không còn ai trong hàng “nghi vấn”. Người đứng đầu hàng “khả tin” lúc này chắc chắn là kỹ sư tin học.
Theo cách làm này, sau mỗi câu hỏi ta thấy rằng có ít nhất một người sẽ bị chuyển vào hàng “bị loại”, do vậy sau tối đa n-1 câu hỏi, chúng ta sẽ tìm ra kỹ sư tin học.
Vì sao điều này đúng: nhận thấy rằng mỗi khi cho một cặp vào hàng “bị loại”, ít nhất một trong 2 phải là nhà quản lý, do đó ở mỗi lần hỏi, số lượng kỹ sư tin học ở hai hàng “khả tin” và “nghi vấn” luôn lớn hơn số nhà quản lý, và do vậy khi hàng “nghi vấn” trống thì người đứng đầu hàng “khả tin” phải là kỹ sư tin học.
Với chiến thuật này, ta có thể dừng trước 1 bước: khi hàng “nghi vấn” còn 1 người, nếu hàng “khả tin” không có ai, người còn lại này chính là kỹ sư tin học, ngược lại, người đứng đầu hàng “khả tin” là kỹ sư tin học. Do vậy, chỉ cần n-2 câu hỏi.
Với n chẵn, ta có thể loại bỏ 1 người bất kỳ và áp dụng cách làm trên với n-1 người còn lại với n-3 câu hỏi. Đáp án này có thể chứng minh là tối ưu.
Đáp án câu 2. Nếu như tất cả các nhà quản lý đều nói dối thì không thể xác định ra ai là ai khi số lượng nhà quản lý lớn hơn số kỹ sư tin học.