Multi-lingual guests puzzle !

To attend a congress , 1000 guests from countries around the world arrived. It is known that ANY 3 guests can speak among themselves without the need of any interpreter( it might happen that one of them would act as as interpreter for the other two persons). But the problem is that the hotel has only 500 double bedrooms. Is it possible to pair up all the guests and put them in those 500 bedrooms so that each pair can talk to each other without any help from interpreter

Hmm. Consider the counter-arrangement

This one is easy. Take three guests at random. Obviously, thay make at least one pair that can talk to each other. Put that pair in room 1. Take a new couple from the crowd and add them to the guy left over. Again, choose a pair. Repeat this until you are left with only four people.

Now, take any three of them. There is at least one of them that can speak with both others. Name him A, the other two B and C, the fourth D. Now we know that A-B and A-C are valid pairings.

Now observe a group B-C-D. Again, it's obvious that D can speak with either B or C, so either D-B or D-C is a good pair. We put them in one room. The pair left is either A-C or A-B, and we know that they match, so the problem is solved.

I noticed that for each guest there can only be at most one guest with whom he shares no common language. If there were two guests that shared no common language with him, then that would make a group of three who could not speak among themselves.

So my algorithm for filling the rooms is:-

Choose random guest as the first occupant of room 1.

Find the person with whom he shares no common language (or choose randomly if there is none). Place this person in room 2.

You can now choose anyone else as the second occupants of these two rooms, since they all share a common language with these two guests.

Repeat the process for each pair of rooms.

Step 1

Step 2

Step 3

This doesn't work if you choose randomly in step 2.

Yes it does. If you chose randomly on step 2, it means that the two guests already in the room are able to communicate with each other. Since any other guest must be able to communicate with at least one of them, they still are all applicable choices.

Eytan

That was my reasoning too.

Hmm, from a 'rigorous' point of view, it is not clear that the last step is possible at all

I assume you mean 'the two guests already in the rooms'.

Any one of the crowd is able to communicate with one of the guests in the rooms. This does not imply that you can 'choose anyone as the second occupants' of these rooms. It is of course easy to prove that any two persons can fill in the two vacant spots - but this wasn't mentioned in the proof.

The last step is always possible, because defining the fact the first two persons you put in the two rooms left, don¹t have a common language assures you that both of the other two can communicate with both of the first two. (Else you'd be able to create a trio that can't communicate...)