Along a round table are arranged $11$ cards with the names ( all distinct ) of the $11$ members of the $16^{th}$ JBMO Problem Selection Committee . The cards are arranged in a regular polygon manner . Assume that in the first meeting of the Committee none of its $11$ members sits in front of the card with his name . Is it possible to rotate the table by some angle so that at the end at least two members sit in front of the card with their names ?
Problem
Source:
Tags: combinatorics
04.02.2015 18:02
While rotating $2\pi$, each card will be in front of its host exactly one time, so 11 members will be in front of the card with his name. However, since there is none of them in front of the right card at first, done by PHP.
28.09.2015 00:48
Since the cards are originally in the wrong place, we turn the table ten times, each time moving one turn right or left. Among these ten turns, there must be one where the card is placed in the right place, for each card. Suppose the sequence is defined as : G if it is placed in the right place, and B if wrong. Thus there can be altogether ten such places for G, ie., BBBBBBBBBR, BBBBBBBBRB,etc. However, since there are 11 cards, atleast two cards have same sequence. Done.
28.09.2015 00:49
combidude wrote: Since the cards are originally in the wrong place, we turn the table ten times, each time moving one turn right or left. Among these ten turns, there must be one where the card is placed in the right place, for each card. Suppose the sequence is defined as : G if it is placed in the right place, and B if wrong. Thus there can be altogether ten such places for G, ie., BBBBBBBBBG, BBBBBBBBGB,etc. However, since there are 11 cards, atleast two cards have same sequence. Done.
04.05.2021 13:52
It is just a more complicated version of the pigeonhole principle... In the beginning, there is no card correctly placed, and we turn the table 10 times one place to the right (or to the left), thus there are 11 people and cards while there are 10 turns on which every person of the Comitee must have seen the cand with his name in front of him exactly once. So in at least one turn 2 members og the Comitee will see their names at the same time!
15.12.2023 14:06
I will give a proof to a more generalized problem. Generalized Problem wrote: Let $n\ge3$ be a positive integer, the numbers $1$ to $n$ are placed on the vertices of an $n$-sided polygon consecutively. If all the numbers are rearranged such that there are no numbers on the same vertice as the initial arrangement, prove that the numbers can be rotated following the order such that there are at least two numbers that are on the same place as the initial arrangement. Let $a_1, a_2,\cdots, a_n$ be the numbers on the vertices of the $n$-sided polygon consecutively such that $a_i=i \ \forall i=1,2,\cdots, n$ initially. Claim. There exist integers $1\le i<j \le n$ such that $a_j-j \equiv a_i-i \ (mod \ n)$. Proof. Consider the set $A$=$\{a_1-1,a_2-2,\cdots, a_n-n\}$. Because $a_i -i\neq 0 \ (mod \ n) \ \forall i=1,2,\cdots, n$, there are at most $n-1$ residue modulo $n$ in $A$. By Pigeon Hole Principle, there are at least two numbers in $A$ that are equal modulo $n$. The claim is proved. If the number $a_j$ are rotated to its initial place $a_{a_j}$, since the order of the numbers are the same, the number $a_i$ will be rotated to the initial place of $a_{f(a_j-j+i)}$ with $f(a_j-j+i)$ being the minimal positive integer satisfying $a_j-j+i \equiv f(a_j-j+i) \ (mod \ n)$. But we have $f(a_j-j+i)=a_i$ since $a_i \le n$. The problem is solved.