ĐỌC VUI VÀ SUY NGHĨ

Cổ vũ lòng yêu thích các trò chơi hữu ích cho sự luyện tập trí óc trong cộng đồng người Việt

CP198 – Câu chuyện về đèn ở 100 lockers



Xưởng đóng bàn ghế ABC có 100 công nhân giúp việc. Xưởng có 100 lockers đặt thẳng hàng dựa vào một bức tường dài. Locker là tủ nhỏ hẹp nhưng cao, có khoá, dành cho công nhân để quần áo và vật dụng cá nhân, mỗi người một locker. Mỗi locker có một số thứ tự và có một bóng đèn nhỏ bên trong cửa có thể bật sáng lên khi cần.

Nhận thấy công nhân thường hay quên tắt đèn, ông giám đốc đem chuyện đó ra bàn luận trong dịp liên hoan cuối năm. Để giúp vui cho buổi tiệc, ông giám đốc đề nghị một trò chơi mà ông nói là đơn giản, để thử tài các công nhân.

Bài toán có nhiều bước như sau:

“Bước thứ nhất, tôi mở tất cả 100 đèn của các lockers.
Bước thứ hai, tôi đi từ đầu đến cuối dãy lockers, đếm nhẩm số các lockers
1, 2, 3, 4, …. và bật contact đèn của lockers có số chẳn. Tức là, nếu đèn đang
sáng thì vặn tắt, nếu đèn đang tắt thì vặn sáng lên.
Bước thứ ba, cũng giống như bước thứ hai, nhưng tắt mở contact đèn của các
lockers có số thứ tự là một bội số của 3, tức là 3, 6, 9, 12, ….
Bước thứ tư, cũng giống như bước thứ hai và thứ ba, nhưng tắt mở contact đèn
của các lockers có số thứ tự là một bội số của 4, tức là 4, 8, 12, 16, ….
………
Cứ thế tiếp tục cho đến bước thứ 100, contact của đèn thứ 100 được tắt hay
mở.”

Và câu hỏi của ông giám đốc là:

“Sau khi trò chơi chấm dứt, xin cho biết lockers nào có đèn vẫn còn sáng ?”

*     *     *

Có 2 cách giải: cách giải thăm dò và cách giải lý luận như dưới đây.

Cách giải thăm dò:

Bạn lập 1 bảng có 100 số từ 1 đến 100 và xét tuần tự từng bước một như trong giả thiết. Bạn có thể dùng dấu “+” và “–“ để chỉ tình trạng đèn sáng và đèn tắt . Dấu thay đổi khi contact đèn bật lên hay bật xuống. Trong bảng, “B N” chỉ “Bước N”.

Để ý rằng “Bước N” chỉ ảnh hưởng đến sự tắt mở đèn của các lockers kể từ N.

Vì giới hạn của tờ giấy, bảng chỉ ghi đến locker 13 và Bước 10. Độc giả có thể dễ
dàng ghi tình trạng của các locker còn lại trong những bước còn lại.

image002
Locker nào mà tình trạng ở bước cuối cùng là “+” sẽ có đèn sáng sau khi trò chơi chấm dứt.
Theo bảng giới hạn trên, các locker có đèn sáng sau cùng là 1, 4, 9. Đó là 3 số chính phương, bình phương của 1, 2 vả 3. Độc giả có thể suy rộng ra đến locker 100 và có lời giải cho bài toán của ông giám đốc. Đèn sáng ở những lockers có số là số chính phương.

Khi trò chơi chấm dứt, đèn của các locker sau đây vẫn còn sáng:

1, 4, 9, 16, 25, 36, 49, 64, 81 và 100

Cách giải bằng lý luận:

Tình trạng tắt sáng của đèn ở locker 64 thay đổi ở những bước 1, 2, 4, 8, 16, 32 và 64, tức là thay đổi 7 lần và bước 64 cuối cùng ứng với dấu “+”, tức là đèn ở locker 64 sáng khi trò chơi chấm dứt. Những bước 1, 2, 4, …, 32, 64 làm thay đổi tình trạng tắt sáng của đèn ở locker 64 đều là những ước số của 64.

Tình trạng tắt sáng của đèn ở locker 42 thay đổi ở những bước 1, 2, 3, 6, 7, 14, 21 và 42, tức là thay đổi 8 lần và bước 42 cuối cùng ứng với dấu “-”, tức là đèn ở locker 42 tắt khi trò chơi chấm dứt. Những bước 1, 2, 3, …, 21, 42 làm thay đổi tình trạng tắt sáng của đèn ở locker 42 đều là những ước số của 42.

Tóm lại, tình trạng tắt sáng của đèn ở locker M chỉ thay đổi ở những Bước N khi N là một ước số của M, kể cả 1 và M. Khi số ước số nầy là một số lẻ thì đèn ở locker M sẽ sáng sau khi trò chơi chấm dứt. Tất cả các số chính phương từ 1 đến 100 đều có tính chất nầy. Mời quý độc giả kiểm chứng lại.

Thuận Hoà
Sydney 2015

 

 

 
%d bloggers like this: