7
$\begingroup$

Suppose there are infinitely many coaches with infinitely many members in each coach. They stay at the hotel for infinitely many days. I know that guests can be accommodated using various methods like the prime powers method, but there's a slight variation in the question which is that the guests have to change their room every day such that one guest can't occupy the same room again (i.e., they have to occupy unique rooms every day). How can we achieve that?

I tried solving the problem using the following method:

  1. I allotted rooms using the prime powers method.

  2. The next day, guests move from their current room $x$ to the new room $x+c$.

I'm struggling after this step. Can someone please help me out?

$\endgroup$
4
  • 4
    $\begingroup$ I assume that whenever you write “infinite” you mean “infinitely many”, right? Remember, “infinite” is a property like ”odd”, not a number like “five”. $\endgroup$
    – celtschk
    Commented Apr 14, 2020 at 6:23
  • 4
    $\begingroup$ As a remark, the word everyday means "humdrum, ordinary, expected": it was an everyday event. The two-word phrase every day means, well, every day. $\endgroup$
    – TRiG
    Commented Apr 14, 2020 at 15:29
  • 1
    $\begingroup$ What do the coaches have to do with anything? Do they all arrive on the same day? Or one each day? $\endgroup$
    – Carsten S
    Commented Apr 14, 2020 at 15:54
  • $\begingroup$ @Carsten: I believe you have to assign rooms to the passengers arriving on the first coach before you assign rooms to the passengers arriving on the second coach, and so on for all the coaches. So you need to come up with a way of mapping the $j^\text{th}$ passenger on the $i^\text{th}$ coach to a room on the first night. On subsequent nights it seems not to matter which coach a passenger arrived on. As far as I can tell, only Kevin's answer addresses this. $\endgroup$
    – Will Orrick
    Commented Apr 14, 2020 at 22:47

3 Answers 3

Reset to default
11
$\begingroup$

A far simpler approach than prime powers is as follows. Number the rooms starting from $0$. Each day,

  • guests in even-numbered rooms move two rooms up
  • guests in odd-numbered rooms move two rooms down, except for the one in room $1$, who moves to room $0$

This creates an infinite cycle linking every room, on which all guests move: $$\dots\to5\to3\to1\to0\to2\to4\to6\cdots$$ So not only is it possible to have all guests occupy different rooms on infinitely many days, it is possible to achieve full utilisation while doing so for all eternity.

If all rooms can only ever be occupied by at most one guest, the following construction (also simpler than prime powers) still ensures that every room is eventually used. Arrange the rooms in an array like this, and this time start from $1$: $$\begin{array} 01&2&4&7&11&\dots\\ 3&5&8&12&17&\dots\\ 6&9&13&18&24&\dots\\ 10&14&19&25&32&\dots\\ 15&20&26&33&41&\dots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}$$ On the first day, the guests stay in triangular-numbered rooms, i.e. the first column of the above array. Each subsequent day, all guests move to the room that is to their immediate right in the array, e.g. $6$ moves to $9$, then to $13$ and $18$, etc.

Both solutions here are based on canonical bijections to $\mathbb N$, from $\mathbb Z$ and $\mathbb N^2$ respectively.

$\endgroup$
8
  • $\begingroup$ My interpretation of the question was that each room can only be occupied at the most once by any guest. This is why I proposed my answer (including stating "a unique room compared to all other guests"), which accomplishes this, & it's the basis for my comments to the OP re: how this is, I believe, relatively difficult to achieve using other means. However, if you allow reuse of rooms by other guests, your method will work, as well as many other relatively simple ones. However, it's not completely clear what the question intent was, so it's definitely possibly I misinterpreted what was wanted. $\endgroup$
    – John Omielan
    Commented Apr 14, 2020 at 5:49
  • $\begingroup$ @JohnOmielan I've made an edit that addresses your interpretation, with a simpler solution than prime powers still. $\endgroup$
    – Parcly Taxel
    Commented Apr 14, 2020 at 6:17
  • $\begingroup$ That's an interesting different way to address assigning rooms based on my more restrictive interpretation of the question. As for being a "simpler solution", I guess that depends on how you define "simpler", e.g., in terms of how it's stated or how to implement it. Regardless, though, your alternate solution is a good one. $\endgroup$
    – John Omielan
    Commented Apr 14, 2020 at 6:25
  • 1
    $\begingroup$ @JohnOmielan I qualify my solution as simpler because I only need repeated addition to calculate the new room numbers, not repeated multiplication (and a prime table for initialisation). $\endgroup$
    – Parcly Taxel
    Commented Apr 14, 2020 at 6:27
  • $\begingroup$ Does this answer completely answer the question? I'm not seeing where it addresses the issue of the guests arriving in infinitely many coaches, each holding infinitely many passengers. This will affect how you assign the guests to rooms on the first night. $\endgroup$
    – Will Orrick
    Commented Apr 14, 2020 at 22:47
5
$\begingroup$

Have guest $i$ on day $j$ stay in room number $p_i^j$, where $p_i$ is the $i$'th prime. The fundamental theorem of arithmetic shows that each guest stays in a unique room compared to all other guests and to their own previous occupied rooms.

Update: As reminded by Will Orrick's comment below, I should have been clear about how to appropriately assign specific guest identifiers ($i$ used above) for the "infinitely many coaches with infinitely many members in each coach". This assumes all of the coaches arrive & can be accessed at the same time, as even the tiniest finite delay in time between coaches means not all of the coaches can arrive in one day. With this assumption, let $c_{m,n}$ be the $n$'th member of coach $m$, with $m,n \ge 1$. Next, order the coach members as shown below

$$\begin{array} 0c_{1,1} & c_{1,2} & c_{1,3} & c_{1,4} & c_{1,5} & \dots\\ c_{2,1} & c_{2,2} & c_{2,3} & c_{2,4} & c_{2,5} & \dots\\ c_{3,1} & c_{3,2} & c_{3,3} & c_{3,4} & c_{3,5} & \dots\\ c_{4,1} & c_{4,2} & c_{4,3} & c_{4,4} & c_{4,5} & \dots\\ c_{5,1} & c_{5,2} & c_{5,3} & c_{5,4} & c_{5,5} & \dots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$

Assign each guest number in turn, start at $i = 1$ at $c_{1,1}$, then going right to $c_{1,2}$ (for $i = 2$), down to $c_{2,2}$ (for $i = 3$), left to $c_{2,1}$, then down to $c_{3,1}$, right until $c_{3,3}$, then up until $c_{1,3}$, then right to $c_{1,4}$, then down to $c_{4,4}$, then left to $c_{4,1}$, etc. As you can see, this snakelike type pattern will cover all of the entries above (by going through all entries of the edges of an increasing square-like pattern), and will eventually get to any $c_{m,n}$ coach member exactly once. This shows one bijection (among other possible ones) between the assigned guest numbers and all of the infinitely many coach members among all of the infinitely many coaches.

Note the method I used is similar to some arguments used to prove the cardinality of the set of rational numbers is the same as the set of the integers, like what this answer of All sets of rational numbers are bigger than the set containing infinite integers - or are they? uses.

$\endgroup$
6
  • $\begingroup$ thank you so much! But i was wondering if we could come up with a sequence such that if we add or subtract any number from the elements, we get a unique room everyday $\endgroup$
    – aussiegirl1995
    Commented Apr 14, 2020 at 5:08
  • 1
    $\begingroup$ @aussiegirl1995 You're welcome. I haven't given it much thought, but I don't think you will be able to determine a sequence where you add or subtract a fixed number. I believe even using some variable number instead will at least be quite difficult as well. Nonetheless, there are many very talented & knowledgeable members here, so somebody may come up with a system like that. $\endgroup$
    – John Omielan
    Commented Apr 14, 2020 at 5:11
  • $\begingroup$ could you suggest a way allocating rooms apart from the prime powers method such that I can use the addition or subtraction operation to calculate new unique rooms everyday? $\endgroup$
    – aussiegirl1995
    Commented Apr 14, 2020 at 5:11
  • $\begingroup$ @aussiegirl1995 See my answer. $\endgroup$
    – Parcly Taxel
    Commented Apr 14, 2020 at 5:43
  • $\begingroup$ Does this answer completely answer the question? I'm not seeing where it addresses the issue of the guests arriving in infinitely many coaches, each holding infinitely many passengers. This will affect how you assign the guests to rooms on the first night. $\endgroup$
    – Will Orrick
    Commented Apr 14, 2020 at 22:47
3
$\begingroup$

There's another option. With the Prime Powers method, you're relying on:

  • No prime, to any power, is equal to any other prime to any power.

Which makes if you think about it from a prime factorization perspective. Each number has exactly one prime factorization. So if you generate a number by taking a prime number X to the power of Y - it's factorization is X, Y times. That'll obviously be a different prime factorization than a prime number A to the Bth power.

But once you think about it in terms of prime factorization, you'll realize you've got a lot of open space. After all... the 6th room will never be filled.

Why? Because 6's prime factorization involves two different primes - so you can't get to it by taking any prime X to the power Y.

So - you've got an infinite number of coaches with an infinite number of people... and they're arriving every day to stay forever?

On the first day, you're set. Each coach gets a different prime number, and each person from that coach gets a different power of that prime.

The second day? Each coach gets a different prime and the next prime higher than it, multiplied together. So the first coach gets 6 - and each of its infinite occupants gets a different power of 6. The next coach gets 15 (3x5). The third coach gets 35 (5x7).

The third day? Each coach gets a different prime and the second prime after it. (So the coaches that day would be: 10, 21, 55, ...) Fourth day? Each coach gets a different prime and the third prime after it. (So the coaches would be: 14, 33, 65, ...)

You've got an infinite number of days covered.

In fact... we covered those infinite days simply by using only two different primes.

(We don't even have to stop there. Imagine we were asked to solve this problem... across an infinite number of universes. Universe #1 uses two primes. Universe #2 uses three primes. Universe #4 uses four primes. Etc.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .