返回题库

希尔伯特旅馆

Infinity & Beyond

专题
Strategy / 策略
难度
L4

题目详情

有一家只有一层、房间编号为 1,2,3,…1,2,3,\dots 的旅馆，并且现在所有房间都住满了。

  1. 来了 1 位新客人，如何安排？
  2. 来了无限多位新客人，如何安排？
  3. 来了无限多辆大巴，每辆车上又有无限多位客人，如何安排？

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied.

  1. A new customer wants to check in, how will you accommodate her?
  2. What if infinite number of people want to check in, how will you accommodate them?
  3. Suppose infinite number of buses arrive at the hotel, each having infinite number of people, how will you accommodate them?

Hint

Define Infinity ;)

解析

  1. 让原本住在 kk 号房的客人搬到 k+1k+1 号房，腾出 1 号房。

  2. 让原本住在 kk 号房的客人搬到 2k2k 号房，所有奇数房间空出来用于安置新客。

  3. 将“(车号, 车内座号)”建立到自然数的一一映射（例如 Cantor 配对函数），把每位新客映射到一个唯一房号即可。

Original Explanation

Solution

  1. Since there are infinite number of rooms and infinite+1= infinite

Just ask person in room k to move to k+1, thus making the first room vacant. :)

  1. In the other case, since infinite+infinite = infinite

asking person in room k to move to 2k solves the problem.

  1. Since NxN is countable set. We can get a 1-1 mapping from N to NxN

Hence, we can accommodate (infinite people X infinite buses) in the hotel.

Relevant article: http://en.wikipedia.org/wiki/Cantor_pairing_function