[bushindo]

You're Q, a pan-dimensional being living in the Q Continuum. Unlike other beings on the Q Continuum who have nothing better to do but going to lower dimensions and bothering mortals on spaceships, you actually have a day job. Your job is to manage the Infinity Inn, which is a hotel with, you guessed it, an infinite number of rooms. Let's say the rooms are numbered from 1 to infinity.

One day, your Infinity Inn is fully booked, but an infinite number of guests arrive. The new guests each wear a shirt with a unique whole number (ie. 1, 2, 3, 4, ... ) . Not one to miss a beat, you ask every currently settled guest to move into a room twice their current number. So the guest currently in room 2 moves into room 4, the guest in room 3 moves into room 6, and so on. The new guests then simply move into the now vacated room. For convenience, you simply ask the new guests to move into room (i*2 - 1), where i is the number on their shirt.

The next day, a family called the Fractions arrived. Each member of the family wears a number of their shirt. For every possible two whole numbers a and b, there is a unique family member who wears a shirt with the number "a/b". So for instance, pick a = 2, and b = 4, there's a guest with 2/4 on hist shirt. Pick a =1001, and b = 23, there's a guy with 1001/23 on his shirt too.

The head of the Fraction family look at your Inn and said that it is too small for his family, not to mention the fact that it is already full. The family was about to leave you said "Wait....".

1 ) Is there a way to fit the whole family inside your inn? Remember, you just fully booked it the night before. If so, describe a way to fit everyone in.

Edited May 26, 2009 by bushindo

[Guest]

Yes. The set of rational numbers is countable:

1/1 1/2 1/3 1/4 .....

2/1 2/2 2/3 2/4.....

3/1 3/2 3/3 3/4....

4/1 4/2 4/3 4/4.....

.

.

.

(create an ordering by 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1 ...following the same diagonal pattern). Then just fit them in as you did with the countably infinite number of guests the previous day.

To come up with a rule that will "work" for assigning rooms, you can have each current occupant move to their room number squared. This means that the occupants in rooms n and n+1 will now be in rooms n^2 and (n+1)^2. Thus there are now (n+1)^2 - n^2 = 2n + 1 empty rooms between n^2 and (n+1)^2.

From the pattern of fractions above you can see that there are n-1 fractions "a/b" such that "a+b = n". Thus, the n -1 people with fractions on their shirts whose numerator and denominator add up to n can be placed in the 2n +1 (only n-1 needed) empty rooms between n^2 and (n+1)^2 in the order according to their numerators 1, 2, 3, ....., n-1.

Edited May 26, 2009 by birleis

[Guest]

couldn't you just reuse your first solution, have everone already in a room move into (let R be thier room number and R' be thier new number)2R=R'

the Fraction Family can move into (Bi*2)-1.

in simpiler terms all the guests already there are shifted to all the even numbers, all the fraction family is moves into all the odd numbers.

a second thought (and this might go against the spirit of the teaser, if so i'm sorry,) it was never said that there could not be a fraction room number, if this is not to nitpicky then they can just move into the room of which there number is assigned.

[Guest]

This is a classic Cantor problem.

Of course there is room -- there are an infinite number of rooms.

First, make room for the new arrivals the same way as for the previous group: have each person move to the room number that is double there current room number. Now half the hotel is vacant. Arrange the new guests as follow:

1/1 1/2 1/3 1/4 . . .

2/1 2/2 2/3 2/4 . . .

3/1 3/2 3/3 3/4 . . .

4/1 4/2 4/3 4/4 . . .

. . . .

. . . .

. . . .

Start in the upper left corner, and put 1/1 in the first available room (Room 1), then start working up and down diagonally, so the order will be 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, and so on. The key is to be able to order the fractions so you can map them to the rooms.

Georg Cantor used this to demonstrate that the set of rational numbers has the same order of infinity (same Cardinal number) as the set of integers.

[Guest]

Yes. The set of rational numbers is countable:

1/1 1/2 1/3 1/4 .....

2/1 2/2 2/3 2/4.....

3/1 3/2 3/3 3/4....

4/1 4/2 4/3 4/4.....

.

.

.

(create an ordering by 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1 ...following the same diagonal pattern). Then just fit them in as you did with the countably infinite number of guests the previous day.

To come up with a rule that will "work" for assigning rooms, you can have each current occupant move to their room number squared. This means that the occupants in rooms n and n+1 will now be in rooms n^2 and (n+1)^2. Thus there are now (n+1)^2 - n^2 = 2n + 1 empty rooms between n^2 and (n+1)^2.

From the pattern of fractions above you can see that there are n-1 fractions "a/b" such that "a+b = n". Thus, the n -1 people with fractions on their shirts whose numerator and denominator add up to n can be placed in the 2n +1 (only n-1 needed) empty rooms between n^2 and (n+1)^2 in the order according to their numerators 1, 2, 3, ....., n-1.

Good job birleis, you beat me to the punch! (I not a very fast typist )

[Guest]

in this dimension infinity is a feasible number of concrete objects so in this hotel there can be a room infinity by infinity by infinity acres big (i think that means 4 dimensional) , name it room number -1. empty all your rooms and put all the new and old guest in there then give each person a keg and go to bed

[Guest]

question, will mine still work

[Guest]

Good job birleis, you beat me to the punch! (I not a very fast typist )

ha. it is because of the extra ellipses in your solution.

[Guest]

Of course! An infinite number of people fit inside. Maybe new rooms magically appear for each guest that needs a room, so it is always full, but there is always space

[bushindo]

in this dimension infinity is a feasible number of concrete objects so in this hotel there can be a room infinity by infinity by infinity acres big (i think that means 4 dimensional) , name it room number -1. empty all your rooms and put all the new and old guest in there then give each person a keg and go to bed

You might be a pan-dimensional being, but you're still a business man first. Giving an infinite number of guests 1 keg each can really cut into your profit, you know. Although you can probably recoup the cost by giving each drunken guest a typewriter and have them churn out shakespeares and stuffs.

[Guest]

I may have completly missed this,(which is most likely) but..

You tell them to take room #i*2-1 (where i is the # on their shirt). Well if the fraction guy with 2/4 on his shirt walks in..2/4*2/1=1 now subtract 1 and you get zero. How does he occupy room #0, especially when the rooms start at #1-infinity?

[bushindo]

I may have completly missed this,(which is most likely) but..

You tell them to take room #i*2-1 (where i is the # on their shirt). Well if the fraction guy with 2/4 on his shirt walks in..2/4*2/1=1 now subtract 1 and you get zero. How does he occupy room #0, especially when the rooms start at #1-infinity?

The part about each guest taking room (2*i - 1) was the instruction for night 1, when guests bearing numbers 1,2,3,4,5,... arrived. The guests with shirts bearing fractions arrive on the second night, and we're supposed to find the solution for that case.

[Guest]

Well, basically you are asking us to prove that the set of rational numbers is countable.

The solution is very simple. Assume the people who are already in the rooms to be wearing shirts with the number (Room number)/1 i.e. a guy in room 2 is assumed to wear a tshirt 2/1.

Now, all you need to do is:

1. ask guest his tshirt no

2. Get reply a/b. Compute (2^a)*(3^b) and assign the guest to this room no.

As the number is unique for every (a,b) and also as the resultant room no. has to be a whole number with a unique prime factorization, you get a unique room for each guy.

Edited May 26, 2009 by Krashe

[Guest]

Hi,

i am new at this but i think it might work.

if you look at what you did to the previous guests you basically moved some to odd number rooms and some to even number room. thus you have the full sequence of numbers 1,2,3,4,5,... filled.

the trick is to look at all the old guests as one set and move them again to odd or even rooms. so you tell each guest in a room to move into his room number*2

then for the fraction family, as it is stated their numbers are a/b, so change their numbers to ab, you concatinate the numbers and you ask them to move into the rooms with the number equivilant to the (new number*2)-1

at the end you will be able to move them all and you will still have rooms number 1,3,5,7,9,11,13,15,17,19 empty since the least number the fraction family can have is 1/1 so the room numbr will be (11*2)-1 = 21

[Guest]

Edit: bad idea, nevermind

Edited May 26, 2009 by James8421

[Guest]

Yes. The set of rational numbers is countable:

1/1 1/2 1/3 1/4 .....

2/1 2/2 2/3 2/4.....

3/1 3/2 3/3 3/4....

4/1 4/2 4/3 4/4.....

.

.

.

(create an ordering by 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1 ...following the same diagonal pattern). Then just fit them in as you did with the countably infinite number of guests the previous day.

To come up with a rule that will "work" for assigning rooms, you can have each current occupant move to their room number squared. This means that the occupants in rooms n and n+1 will now be in rooms n^2 and (n+1)^2. Thus there are now (n+1)^2 - n^2 = 2n + 1 empty rooms between n^2 and (n+1)^2.

From the pattern of fractions above you can see that there are n-1 fractions "a/b" such that "a+b = n". Thus, the n -1 people with fractions on their shirts whose numerator and denominator add up to n can be placed in the 2n +1 (only n-1 needed) empty rooms between n^2 and (n+1)^2 in the order according to their numerators 1, 2, 3, ....., n-1.

Great logic puzzle, I liked the originality you used to present cardinality, it would probably be a great way to teach this.

birleis already solved it, but I just came up with an exact rule for numbering everyone.

While moving everyone to their square works great, it will leave us with a bunch of empty space (an infinite amount, in fact) and because we are a business man we can avoid this by moving everyone into the summation from 1 to their number.

Here are the first few.

Old Room Number over New Room Number:

1 2 3 4 5 6

1 3 6 10 15 21

Now simply move every fraction into the [summation from 1 to (numerator + denominator - 1)] + numerator

A couple examples:

1/3 :: 1 + 3 - 1 = 3 :: summation of 1 to 3 = 6 :: 6 + 1 = 7 :: 1/3 moves into room 7

7/5 :: 7 + 5 - 1 = 11 :: summation of 1 to 11 = 66 :: 66 + 7 = 73 :: 7/5 moves into room 73

Here are the first few.

Fraction over New Room Number

1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 1/5 2/4 3/3 4/3 5/2 6/1

2 4 5 7 8 9 11 12 13 14 16 17 18 19 20 21

Hopefully, everyone can see how I did this, and look no extra space! Again, birleis in the above spoiler did all the difficult explaining of the concepts.

P.S. I don't think everyone realizes that this would be an impossible problem if an infinite number of guests came with shirts labeled with real numbers.

Edited May 26, 2009 by iangardner777

[Guest]

Old Room Number to New Room Number:

1 - 1

2 - 3

3 - 6

4 - 10

5 - 15

6 - 21

Fraction to New Room Number (and I made a mistake in this one above):

1/1 - 2

1/2 - 4

2/1 - 5

1/3 - 7

2/2 - 8

3/1 - 9

1/4 - 11

2/3 - 12

3/2 - 13

4/1 - 14

1/5 - 16

2/4 - 17

3/3 - 18

4/2 - 19

5/1 - 20

[Guest]

learn from the bible? put the new arrivals in the stable. It worked 2000 years ago, it'll work now

[Guest]

well now for the fraction family, u can first ask all the previous guests to again move into a room twice the value of their previous one ( person in room 4 goes to 8) thus ensuring they occupy the even rooms.

Now u ask the fraction family to go to a room of value [{(a/b*b)*2}+1] where a/b is the fraction on their tees

of course this will only work provided the whole no 'a' of the fraction a/b on the family members' tees all have a unique value ...or some of dem might need to share XP

Edited May 27, 2009 by Sapientia

[Guest]

The head of the Fraction family look at your Inn and said that it is too small for his family, not to mention the fact that it is already full. The family was about to leave you said "Wait....".

1 ) Is there a way to fit the whole family inside your inn? Remember, you just fully booked it the night before. If so, describe a way to fit everyone in.

The first floor (call it floor zero) is full. Let the denominator represent an infinite number of other floors, and the numerator represent the room number on each floor.