The International Mathematical Olympiad is being organized in Japan, where a folklore belief is that the number $4$ brings bad luck. The opening ceremony takes place at the Grand Theatre where each row has the capacity of $55$ seats. What is the maximum number of contestants that can be seated in a single row with the restriction that no two of them are $4$ seats apart (so that bad luck during the competition is avoided)?
Problem
Source: Balkan BMO Shortlist 2014 C1
Tags: combinatorics
chocolatelover111
06.08.2019 07:31
Four seats means four are in between the contestants, right?
Call the chairs $c_1,c_2,\dots,c_{55}$.
We put the chairs into mod $5$ groups:
$c_1,c_6,c_{11},\dots,c_{51}$
$c_2,c_7,c_{12},\dots,c_{52}$
$c_3,c_8,c_{13},\dots,c_{53}$
$c_4,c_9,c_{14},\dots,c_{54}$
$c_5,c_{10},c_{15},\dots,c_{55}$
Note that each residue group has $11$ chairs. The restriction of being $4$ seats apart is equivalent for any two consecutive seats in a residue to not both have a contestant.
We can group the $11$ chairs in a residue group into $5$ pairs of consecutive chairs and one more chair, so there are at most $6$ pairs of chairs. This is achievable: consider $OVOVOVOVOVO$ where O=occupied and V=vacant.
Thus, the maximum is $6\cdot5=\boxed{30}$
GoodMorning
06.08.2019 07:38
I'm getting a different answer
We assign each seat a number. Therefore, the numbers are 1-55. We consider this in four groups (I know we don't need to do this, but it makes it easier to prove) The four cases don't interfere with each other, so its convenient.
1. Consider the seats who's number mod 4 is 0.
There are $\lfloor \frac{55}{4} \rfloor= 13$ of those seats. We can't have two consecutive multiples of $4$. Therefore, the greatest amount of seats we can actually seat people in is $\lfloor \frac{13}{2} \rfloor= 7$
2. Consider the seats who's number mod 4 is 1
There are $14$ of those seats. Similarly we can't have two consecutive multiples of $4$.THerefore, the greatest amount of seats who's number mod 4 is 1 that we can actually seat people in is $\lfloor \frac{14}{2} \rfloor= 7$
3. Similarly, we get $7$.
4. We also get $7$.
So the answer is $7 \times 4 = \boxed{28}$
chocolatelover111
06.08.2019 07:40
@above I think you're correct, I thought 4 seats apart meant $4$ seats in between
Neo-Pythagorean
15.08.2021 00:00
Actually, the interpretation of the problem by @chocolatelover111 is the correct one according to the official solution. Although, I have to admit that the problem statement is ambiguous (for example, I understood the same thing with @GoodMorning).
AriizuZDR
08.10.2021 07:37
Let $a_i$ where $i=\{1,2,...55\}$ be the seats. Then if someone occupies the $a_k$th place, the $a_{k+5}$th place has to be empty. But which chairs don't have an $a_{k+5}$th place? They are $a_{51}$, $a_{52}$, $a_{53}$, $a_{54}$, $a_{55}$. So we take these out for now. For seats $a_i$ where $i=\{1,2,3...,50\}$, if there are $k$ seats taken there should be $k$ seats empty, then $2k=50 \Rightarrow k=25$, $25$ seats occupied. We get maximum if we can use the chairs $a_{51}$, $a_{52}$, $a_{53}$, $a_{54}$, $a_{55}$ maximally somehow, but the following example shows that all $5$ of these chairs can indeed be used, making $30$: $$1\hspace{0.1cm}2\hspace{0.1cm}3\hspace{0.1cm}4\hspace{0.1cm}5 \underbrace{...}_{5 seats}6 \hspace{0.1cm}7\hspace{0.1cm}8\hspace{0.1cm}9\hspace{0.1cm}10......51\hspace{0.1cm}52\hspace{0.1cm}53\hspace{0.1cm}54\hspace{0.1cm}55$$
CrazyInMath
05.02.2023 09:27
Number the seats from $1$ to $55$. Notice that the seats that are not congruent mod $5$ would not affect each other.
So we get $5$ types of seat with $11$ of each type.
Now we $2$-color each type to found that $6$ seats could be occupied each type.
So the answer is $6\times5=30$.
GeorgeRP
07.07.2023 01:36
Let there be \(n\) seats, and the unlucky number be \(k\). We see that the seats "affect each other" only if they give the same residue modulo \(k\). Now we have \(k\) groups, \(\{\frac{n}{k}\}.k\) of which have \(\lceil \frac{n}{k} \rceil\) seats, and the rest having \(\lfloor \frac{n}{k} \rfloor\) seats. Double colouring gives us that we can at most pick \(k \cdot \left(\lceil \frac{\left\lceil \frac{n}{k} \rceil\right)}{2} \rceil \cdot \{\frac{n}{k}\}+\lceil \frac{\lfloor \frac{n}{k} \rfloor}{2} \rceil \cdot \left(1-\{\frac{n}{k}\}\right)\right)\). Depending on how we interpreted the problem that means that the answer is either 28 or 30.