q,
and m and n are natural numbers, then
pm
qn."Translated by Abe Shenitzer
with the editorial assistance of
Hardy Grant and Stefan Mykytiuk
Birkhäuser
Boston • Basel • Berlin
The extraordinary hotel, or the thousand and first journey of Ion the Quiet. I got home rather late — the get-together at the club Andromeda Nebula dragged on long after midnight. I was tormented by nightmares the whole night. I dreamt that I had swallowed an enormous Kurdl; then I dreamt that I was again on the planet Durditov and didn't know how to escape one of those terrible machines they have there that turn people into hexagons; then . . . People generally advise against mixing old age with seasoned mead. An unexpected telephone call brought me back to reality. It was my old friend and companion in interstellar travels Professor Tarantog.
"A pressing problem, my dear Ion," I heard. "Astronomers have discovered a strange object in the cosmos — a mysterious black line stretching from one galaxy to another. No one knows what is going on. Even the best telescopes and radio-telescopes placed on rockets cannot help in unraveling the mystery. You are our last hope. Fly right away in the direction of nebula ACD-1587."
The next day I got my old photon rocket back from the repair shop and installed in it my time accelerator and my electronic robot who knows all the languages of the cosmos and all the stories about interstellar travel (it is guaranteed to keep me entertained for at least a five-year journey). Then I took off to attend to the matter at hand.
Just as the robot exhausted his entire supply of stories and had begun to repeat himself (nothing is worse than listening to an electronic robot repeating an old story for the tenth time), the goal of my journey appeared in the distance. The galaxies which covered up the mysterious line lay behind me, and in front of me was . . . the hotel Cosmos. Some time ago I constructed a small planet for wandering interstellar exiles, but they tore it apart and again were without a refuge. After that, they decided to give up wandering into foreign galaxies and to put up a grandiose building — a hotel for all travelers in the cosmos. This hotel extended across almost all the galaxies. I say "almost all" because the exiles dismantled a few uninhabited galaxies and made off with a few poorly situated constellations from each of the remaining ones.
But they did a marvelous job of building the hotel. In each room there were faucets from which hot and cold plasma flowed. If you wished, you could be split into atoms for the night, and in the morning the porter would put your atoms back together again.
But, most important of all, there was an infinite number of rooms in the hotel. The exiles hoped that from now on no one would have to hear that irksome phrase that had plagued them during their time of wandering: "no room available."
In spite of this I had no luck. The first thing that caught my eye when I entered the vestibule of the hotel was a sign: Delegates to the cosmic zoologists' congress are to register on the 127th floor.
Since cosmic zoologists came from all the galaxies and there are an infinite number of these, it turned out that all the rooms were occupied by participants in the conference. There was no place for me. True, the manager tried to get some of the delegates to agree to double up so that I could share a room with one of them. But when I found out that one proposed roommate breathed fluorine and another considered it normal to have the temperature of his environment at about 860°, I politely turned down such "pleasant" neighbors.
Luckily the director of the hotel had been an exile and well remembered the good turn I had done him and his fellows. He would try to find me a place at the hotel. After all, you could catch pneumonia spending the night in interstellar space. After some meditation, he turned to the manager and said:
"Put him in number 1."
"Where am I going to put the guest in number 1?"
"Put him in number 2. Shift the guest in number 2 to number 3, number 3 to number 4, and so on."
It was only at this point that I began to appreciate the unusual qualities of the hotel. If there had been only a finite number of rooms, the guest in the last room would have had to move out into interstellar space. But because the hotel had infinitely many rooms, there was space for all, and I was able to move in without depriving any of the cosmic zoologists of his room.
The following morning, I was not astonished to find that I was asked to move into number 1,000,000. It was simply that some cosmic zoologists had arrived belatedly from galaxy VSK-3472, and they had to find room for another 999,999 guests. But while I was going to the manager to pay for my room on the third day of my stay at the hotel, I was dismayed to see that from the manager's window there extended a line whose end disappeared somewhere near the clouds of Magellan. Just then I heard a voice:
"I will exchange two stamps from the Andromeda nebula for a stamp from Sirius."
"Who has the Whale stamp from the 57th year of the cosmic era?"
I turned in bewilderment to the manager and asked:
"Who are these people?"
"This is the interstellar congress of philatelists."
"Are there many of them?"
"An infinite set — one representative from each galaxy."
"But how will you find room for them? After all, the cosmic zoologists don't leave till tomorrow."
"I don't know; I am on my way now to speak to the director about it for a few minutes."
However, this time the problem turned out to be much more difficult and the few minutes extended into an hour. Finally, the manager left the office of the director and proceeded to make his arrangements. First he asked the guest in number 1 to move to number 2. This seemed strange to me, since I knew from my own experience that such a shift would only free one room, whereas he had to find places for nothing less than an infinite set of philatelists. But the manager continued to give orders:
"Put the guest from number 2 into number 4, the one from number 3 into number 6; in general, put the guest from number n into number 2n."
Now his plan became clear: by this scheme he would free the infinite set of odd-numbered rooms and would be able to settle the philatelists in them. So in the end the even numbers turned out to be occupied by cosmic zoologists and the odd numbers by philatelists. (I didn't say anything about myself — after three days of acquaintance I became so friendly with the cosmic zoologists that I had been chosen an honorary representative to their congress; so I had to abandon my own room along with all the cosmic zoologists and move from number 1,000,000 to number 2,000,000). And a philatelist friend of mine who was 574th in line got room number 1147. In general, the philatelist who was nth in line got room number 2n — 1.
The following day the room situation eased up — the cosmic zoologists' congress ended and they took off for home. I moved in with the director, in whose apartment there was a vacant room. But what is good for the guests does not always please the management. After a few days my generous host became sad.
"What's the trouble?" I asked him.
"Half the rooms are empty. We won't fulfill the financial plan."
Actually, I was not quite sure what financial plan he was talking about; after all, he was getting the fee for an infinite number of rooms, but I nevertheless gave him some advice:
"Well, why don't you move the guests closer together; move them around so as to fill all the rooms."
This turned out to be easy to do. The philatelists occupied only the odd rooms: 1,3,5,7,9, etc. They left the guest in number 1 alone. They moved number 3 into number 2, number 5 into number 3, number 7 into number 4, etc. At the end all the rooms were once again filled and not even one new guest had arrived.
But this did not end the director's unhappiness. It was explained that the exiles did not content themselves with the erection of the hotel Cosmos. The indefatigable builders then went on to construct an infinite set of hotels, each of which had infinitely many rooms. To do this they dismantled so many galaxies that the intergalactic equilibrium was upset and this could entail serious consequences. They were therefore asked to close all the hotels except ours and put the material used back into place. But it was difficult to carry out this order when all the hotels (ours included) were filled. He was asked to move all the guests from infinitely many hotels, each of which had infinitely many guests, into one hotel, and this one was already filled!
"I've had enough!" the director shouted. "First I put up one guest in an already full hotel, then another 999,999, then even an infinite set of guests; and now they want me to find room in it for an additional infinite set of infinite sets of guests. No, the hotel isn't made of rubber; let them put them where they want."
But an order was an order, and they had five days to get ready for the arrival of the new guests. Nobody worked in the hotel during these five days — everybody was pondering how to solve the problem. A contest was announced — the prize would be a tour of one of the galaxies. But all the solutions proposed were turned down as unsuccessful. Then a cook in training made the following proposal: leave the guest in number 1 in his present quarters, move number 2 into number 1001, number 3 into number 2001, etc. After this, put the guest from the second hotel into numbers 2, 1002, 2002, etc. of our hotel, the guests from the third hotel into numbers 3, 1003, 2003, etc. The project was turned down, for it was not clear where the guests of the 1001st hotel were to be placed; after all, the guests from the first 1000 hotels would occupy all the rooms. We recalled on this occasion that when the servile Roman senate offered to rename the month of September "Tiberius" to honor the emperor (the preceding months had already been given the names of Julius and Augustus), Tiberius asked them caustically "and what will you offer the thirteenth Caesar?"
The hotel's bookkeeper proposed a pretty good variant. He advised us to make use of the properties of the geometric progression and resettle the guests as follows: the guests from the first hotel are to be put in rooms 2, 4, 8, 16, 32, etc. (these numbers form a geometric progression with multiplier 2). The guests from the second hotel are to be put in rooms 3, 9, 27, 81, etc. (these are the terms of the geometric progression with multiplier 3). He proposed that we resettle the guests from the other hotels in a similar manner. But the director asked him:
"And we are to use the progression with multiplier 4 for the third hotel?"
"Of course," the bookkeeper replied.
"Then nothing is accomplished; after all, we already have someone from the first hotel in room 4, so where are we going to put the people from the third hotel?"
My turn to speak came; it was not for nothing that they made you study mathematics for five years at the Stellar Academy.
"Use prime numbers. Put the guests from the first hotel into numbers 2, 4, 8, 16, . . ., from the second hotel into numbers 3, 9, 27, 81,. . ., from the third into numbers 5, 25, 125, 625,. . ., the fourth into numbers 7, 49, 343,. . .".
"And it won't happen again that some room will have two guests?" the director asked.
"No. After all, if you take two prime numbers, none of their
positive integer powers can equal one another.
If p and q are prime numbers,
p q,
and m and n are natural numbers, then
pm
qn."
The director agreed with me and immediately found an improvement on
the method I had proposed, in which only the primes 2 and 3 were needed.
Namely, he proposed to put the guest from the mth room of the
nth hotel into room number
2m3n. This works because if
m p
or
n q,
2m3n
2p3q.
So no room would have two occupants.
This proposal delighted everyone. It was a solution of the problem that everyone had supposed insoluble. But neither the director nor I got the prize; too many rooms would be left unoccupied if our solutions were adopted (according to mine — such rooms as 6, 10, 12, and, more generally, all rooms whose numbers were not powers of primes, and according to the director's — all rooms whose numbers could not be written in the form 2n3m). The best solution was proposed by one of the philatelists, the president of the Academy of Mathematics of the galaxy Swan.
He proposed that we construct a tabulation, in whose rows the number of the hotel would appear, and in whose columns the room numbers would appear. For example, at the intersection of the 4th row and the 6th column there would appear the 6th room of the 4th hotel. Here is the tabulation (actually, only its upper left part, for to write down the entire tabulation we would have to employ infinitely many rows and columns):
(1,1) (1,2) (1,3) (1,4) (1,5) ... (1,n) ...
(2,1) (2,2) (2,3) (2,4) (2,5) ... (2,n) ...
(3,1) (3,2) (3,3) (3,4) (3,5) ... (3,n) ...
(4,1) (4,2) (4,3) (4,4) (4,5) ... (4,n) ...
(5,1) (5,2) (5,3) (5,4) (5,5) ... (5,n) ...
....................................................
(m,1) (m,2) (m,3) (m,4) (m,5) ... (m,n) ...
....................................................
"And now settle the guests according to squares," the mathematician-philatelist said.
"How?" The director did not understand.
"By squares. In number 1 put the guest from (1,1), i.e., from the first room of the first hotel; in number 2 put the guest from (1,2), i.e., from the second room of the first hotel; in number 3 put the guest from (2,2), the second room of the second hotel, and in number 4 — the guest from (2,1), the first room of the second hotel. We will thus have settled the guests from the upper left square of side 2. After this, put the guest from (1,3) in number 5, from (2,3) in number 6, from (3,3) in number 7, from (3,2) in number 8, from (3,1) in number 9. (These rooms fill out the square of side 3.) And we carry on in this way:
(1,1) (1,2) (1,3) (1,4) (1,5) ... (1,n) ...
¯ ¯ ¯ ¯ ¯
(2,1) ¬ (2,2) (2,3) (2,4) (2,5) ... (2,n) ...
¯ ¯ ¯ ¯
(3,1) ¬ (3,2) ¬ (3,3) (3,4) (3,5) ... (3,n) ...
¯ ¯ ¯
(4,1) ¬ (4,2) ¬ (4,3) ¬ (4,4) (4,5) ... (4,n) ...
¯ ¯
(5,1) ¬ (5,2) ¬ (5,3) ¬ (5,4) ¬ (5,5) ... (5,n) ...
¯
............................................................
(n,1) ¬ (n,2) ¬ (n,3) ¬ (n,4) ¬ (n,5) ¬ ... (n,n) ...
............................................................
"Will there really be enough room for all?" The director was doubtful.
"Of course. After all, according to this scheme we settle the guests from the first n rooms of the first n hotels in the first n2 rooms. So sooner or later every guest will get a room. For example, if we are talking about the guest from number 136 in hotel number 217, he will get a room at the 217th stage. We can even easily figure out which room. It will have the number 2172 - 136 + 1. More generally, if the guest occupies room n in the mth hotel, then if n ³ m he will occupy number (n - 1)2 + m, and if n < m, number m2 - n + 1."
The proposed project was recognized to be the best — all the guests from all hotels would find a place in our hotel, and not even one room would be empty. The mathematician-philatelist received the prize — a tour of galaxy LCR-287.
In honor of this so successful solution, the director organized a reception to which he invited all the guests. The reception, too, had its problems. The occupants of the even-numbered rooms arrived a half hour late, and when they appeared, it turned out that all the chairs were occupied, even though our kind host had arranged to have a chairs for each guest. They had to wait while everyone shifted to new places so as to free the necessary quantity of seats (of course, not one new chair was brought into the hall). Later on, when they began to serve the guests ice cream, it was discovered that each guest had two portions, although, as a matter of fact, the cook had only prepared one portion per guest. I hope that by now the reader can figure out by himself how this happened.
At the end of the reception I got into my photon rocket and took off for Earth. I had to inform the cosmonauts of Earth about the new haven existing in the cosmos. Besides, I wanted to consult some prominent mathematicians and my friend Professor Tarantog about the properties of infinite sets.
The census that never took place. Up to now I have talked about the successes of the director of the extraordinary hotel: about how he managed to find places for an infinite set of new guests in his already full hotel, and how he later was able to find places even for the guests from infinitely many such unusual hotels. But there was a time when even this wizard met failure.
An order came down from the commissioner of cosmic hotels to compile a list as quickly as possible of all the possible ways in which the rooms of the hotel could be occupied. The list was to be presented in the form of a table, each line of which was to reflect one of the various ways of occupying the hotel. The filled rooms were to be indicated by ones and the empty rooms by zeros. For example, the sequence
meant that all the odd rooms were filled and all the even rooms were empty. The sequence
meant that the entire hotel was filled, while the sequence
indicated a financial catastrophe — all the rooms were empty.
The director was overloaded with work and therefore conceived of a simple way out of the situation. He charged the man on duty on each floor to compose a list of the ways in which just the rooms in his charge could be occupied. No two ways on the list were to be the same. After a few days the lists were presented to the director and he combined them all into one list.
"Are you sure that this list is complete?" I asked the director. "Isn't there some other way of occupying the rooms?"
"I don't know" he replied. "There are infinitely many ways listed and I don't know how to test the list for completeness."
At this point an idea flashed into my head (by the way, I may be overestimating my talents, because not all traces of my discussions with Professor Tarantog on infinite sets had vanished from my mind).
"I can guarantee that the list is incomplete. I can select a way that is sure to be lacking."
"I agree that the list is probably incomplete. But you won't succeed in selecting a way that isn't listed; after all, there are already infinitely many listed."
We made a bet. I proposed to win it by nailing each sequence on the door of the room to which it corresponded (the reader will recall that there were just as many ways listed as rooms in the hotel). I then proceeded in a very simple fashion. Going up to the door of the first room, I saw that the corresponding sequence started with the digit 0. The digit 1 quickly appeared on my writing pad; this was the first digit of the sequence I wanted to construct.
When I went up to the door of the second room, I wasn't interested in the first digit of the sequence; after all, I already had the first digit of my sequence. So I directed my attention to the second digit. Seeing that this was 1, I wrote the digit 0 on my pad. Similarly, when I noticed that the third digit of the sequence nailed to the third room was also 1, I again wrote the digit 0 on my pad. In general, when I found that the nth digit of the nth sequence was 0, then I wrote the digit 1 in the nth place on my pad, but if the nth digit of the nth sequence was 1, then I wrote 0.
After I had gone past all the rooms of the hotel* [Hm, how much time did he have to spend?] a sequence of zeros and ones had been written on my pad.
Going to the director's office, I said:
"Here, feast your eyes on the missing sequence."
"And how do you know that it's lacking?"
"It can't be the first because it has a different first digit. It can't be the second because it has a different second digit; in general, it can't be the nth because it has a different nth digit."
The bet was won, and I gained the privilege of staying at the hotel whenever I wanted at no charge.
But it at once became clear that no matter what countable set of sequences you took, there would always be a sequence that didn't appear in the list (you would always be able to hang them on the doors of the rooms). This means that the set of all ways of occupying the hotel is uncountable, and the task given the director was not one that could be carried out.
We decided to send a telegram describing the situation. I should point out that the telegraph in use at the extraordinary hotel was itself unusual: it could send telegrams composed of an infinite set (more precisely, a countable set) of
dots and dashes. For example, the telegram might have the form
I quickly grasped the fact that the set of all such telegrams was also uncountable; after all, you could just as well put zeros and ones in place of the dots and dashes, and then there would be no difference at all between the telegrams with a countable set of signs and the set of all ways of occupying the hotel.
After sending the telegram, I took leave of the director of the hotel and took off for galaxy RGC-8067, where I was to carry out an astrographical survey.