| medium | strategy |
Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied.
- A new customer wants to check in, how will you accommodate her?
- What if infinite number of people want to check in, how will you accommodate them?
- Suppose infinite number of buses arrive at the hotel, each having infinite number of people, how will you accommodate them?
Define Infinity ;)
- 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. :)
- In the other case, since infinite+infinite = infinite
asking person in room k to move to 2k solves the problem.
- 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