CP274 – Nghịch lý Hilbert của đại khách sạn
Khách sạn bình thường chỉ có một số giới hạn các phòng. Khi mỗi phòng đều có người chiếm, người khách mới đến đặt phòng sẽ bị từ chối với lời giải thích là “khách sạn đã đầy”.
Bây giờ, giả sử có một đại khách sạn giả tưởng có vô số đếm được các phòng đánh số 1, 2, 3, . . . . , tức là với một số nguyên n bất kỳ nảo đó, khách sạn có một phòng có số n tương ứng.
Theo lẽ thường, nếu tất cả các phòng đều có khách chiếm, thì một khách mới đến sẽ bị từ chối. Có đúng vậy không? Thưa không, đại khách sạn đều có thể có phòng cho, không phải một, mà bao nhiêu khách mới cũng được!.
Sau đây, mời bạn xem cách người quản lý khách sạn giải quyết các trường hợp khó khăn gặp phải.
Để có phòng cho chỉ một người khách mới, viên quản lý chuyển khách ở phòng 1 sang phòng 2, khách ở phòng 2 sang phòng 3, cứ thế tiếp tục, khách ở phòng n sang phòng (n+1). Như vậy, khách sạn đặt người khách mới vào phòng trống 1.
Để có phòng cho một nhóm 40 khách mới vừa đến từ xe bus, viên quản lý chuyển khách ở phòng 41 sang phòng 42, khách phòng 42 sang phòng 43, …. , khách phòng 80 sang phòng 81. Như vậy, khách sạn đặt 40 khách mới vào các phòng từ 1 đến phòng 40.
Để có phòng cho một toán có vô số khách mới, viên quản lý chuyển khách ở phòng 1 sang phòng 2, khách ở phòng 2 sang phòng 4, khách ở phòng 3 sang phòng 6, vv … Nói cách khác, khách ở phòng n chuyển sang phòng 2n. Như vậy, các khách cũ của khách sạn được chuyển qua các phòng số chẳn và các phòng số lẻ trở nên trống. Tóm lại, khách sạn đặt vô số khách mới vào các phòng 1, 3, 5, 7, vv …. Khách hàng mới n được đặt vào phòng số (2n – 1).
Trường hợp giả tưởng khó khăn mà đại khách sạn phải giải quyết là: khi có vô số xe bus, mỗi xe chở vô số khách đến
khách sạn để đặt phòng. Viên quản lý khách sạn phải giải quyết như thế nào? Bạn thử tự giải quyết xem sao trước khi đọc tiếp.
Đây là cách giải quyết của viên quản lý khách sạn:
1) Chuyển những khách cũ vào những phòng có số phòng là nhũng lũy thừa của 2.
Khách ở phòng 1 chuyển sang phòng 21 = 2, khách ở phòng 2 chuyển sang phòng 22 = 4,
khách ở phòng 3 chuyển sang phòng 23 = 8, vv . . . khách ở phòng n chuyển sang phòng 2n.
2) Gán mỗi xe bus với một số nguyên tố lớn hơn 2. Thí dụ: bus số 1 gán với số 3, bus 2 gán với số 5, bus 3 với số 7, vv . . .
Bus n với số nguyên tố Pn+1
3) Các khách mới trong xe bus được gán cho số α sẽ được đưa vào các phòng có số là những lũy thừa của α.
Thí dụ: Bus số 1 được gán cho số nguyên tố 3. Các khách mới trong xe bus 1 được đưa vào các phòng 31 = 3, 32 = 9, 32 = 27, vv . . .
Bus số 3 được gán cho số nguyên tố 7. Các khách mới trong xe bus 7 được đưa vào các phòng 71 = 7, 72 = 49, 73 = 343, vv . . .
Bảng phân phối các khách cũ và các khách mới trong các xe bus như sau:
ĐỌC VUI VÀ SUY NGHĨ 