wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Round table conference
        
(Message started by: Aryabhatta on Jul 3^rd, 2004, 6:34am)

Title: Round table conference
Post by Aryabhatta on Jul 3^rd, 2004, 6:34am

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.

Title: Re: Round table conference
Post by TenaliRaman on Jul 3^rd, 2004, 9:13am

::[hide]
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.
[/hide]::

Title: Re: Round table conference
Post by THUDandBLUNDER on Jul 3^rd, 2004, 5:11pm

:[hide]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.[/hide]

Title: Re: Round table conference
Post by Grimbal on Jul 3^rd, 2004, 5:23pm

In fact, we should think of pigeons in a circle of holes, and not guests at a table...

Title: Re: Round table conference
Post by Icarus on Jul 21^st, 2004, 7:11pm

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.

Title: Re: Round table conference
Post by Eigenray on Jul 22^nd, 2004, 6:25am

::[hide]
Again consider the n values a_i-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](a_i-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 a_i = n+1-i. Then if a_i-i = n+1-2i == n+1-2j = a_j-j, we must have i == j, because 2 is invertible mod n. Thus, for this seating, there is no good rotation.[/hide]
::

Title: Re: Round table conference
Post by Eigenray on Jul 22^nd, 2004, 10:54am

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 (http://mathworld.wolfram.com/QueensProblem.html), and the sequences A006717 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006717) and A003111 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003111).)
I don't suppose a closed form is known. (More on Cyclic Complete Mappings (http://goedel.csie.ntu.edu.tw/~arping/turing/cm/cm.htm).)