Author |
Topic: Round table conference (Read 613 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Round table conference
« on: Jul 3rd, 2004, 6:34am » |
 Quote  Modify
|
There are n [ge] 2 people attending a round table conference. The organisers of the conference place name cards for each person on the table, but each person goes ahead and sits in a position assigned to someone else. Show that the table can be rotated so that at least two people are in the right position.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Round table conference
« Reply #1 on: Jul 3rd, 2004, 9:13am » |
Quote Modify
|
::
Lets for simplicity assume that the person's are named 1,2,3,4,...,n. Now placards numbered from 1 to n are arranged on the table. Assume ppl sit in some permutation of (1,..,n) say (a1,..,an) in the round table starting from 1 to n.
Consider a1-1,a2-2,a3-3,a4-4,....,an-n
Consider their mods n.
if some of their mods is zero, then that would mean that person is sitting against his own placard which is not correct given the conditions.
therefore there must be atleast 2 values ai-i and aj-j which have equal mods n. therefore,
ai=i+r
aj=j+r
Hence with r rotations ai and aj can have their own placards in front of them.
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Round table conference
« Reply #2 on: Jul 3rd, 2004, 5:11pm » |
Quote Modify
|
:If we let the clockwise displacement of each person from their own seat be k, then max range of k is from
1 to n-1. Hence, as there are n people, at least 2 people must share the same value of k.
|
| « Last Edit: Jul 3rd, 2004, 5:16pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Round table conference
« Reply #3 on: Jul 3rd, 2004, 5:23pm » |
Quote Modify
|
In fact, we should think of pigeons in a circle of holes, and not guests at a table...
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Round table conference
« Reply #4 on: Jul 21st, 2004, 7:11pm » |
Quote Modify
|
Variation:
Show that if n is even, and the guests sit entirely at random, then it is still possible to rotate the table so that at least 2 guests are sitting at their cards.
Conversely, if n is odd, then the guests can sit in a position where only one match exists for any rotation.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Round table conference
« Reply #5 on: Jul 22nd, 2004, 6:25am » |
Quote Modify
|
::
Again consider the n values ai-i. A good rotation exists iff at least two of these values are congruent mod n.
Case 1: n=2k is even.
Let a be any seating permutation, and suppose the values are all different. Then, modulo n,
0 = [sum](ai-i) == 0 + 1 + 2 + . . . + (n-1) = (2k-1)k == k,
which is a contradiction. Thus some two must be the same, and a good rotation always exists.
Case 2: n=2k+1 is odd.
Let ai = n+1-i. Then if ai-i = n+1-2i == n+1-2j = aj-j, we must have i == j, because 2 is invertible mod n. Thus, for this seating, there is no good rotation.
::
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Round table conference
« Reply #6 on: Jul 22nd, 2004, 10:54am » |
Quote Modify
|
The number of arrangements for which it is not possible to rotate the table to have at least 2 correct:
1, 0, 3, 0, 15, 0, 133, 0, 2025, 0, 37851, 0, . . .
If you think about it, this is also the number of ways to arrange n nonattacking semiqueens on an nxn toroidal board.
(See Queens Problem, and the sequences A006717 and A003111.)
I don't suppose a closed form is known. (More on Cyclic Complete Mappings.)
|
| « Last Edit: Jul 22nd, 2004, 11:11am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print