99 dwarfs stand in a circle, some of them wear hats. There are no adjacent dwarfs in hats and no dwarfs in hats with exactly 48 dwarfs standing between them. What is the maximal possible number of dwarfs in hats?
Problem
Source: Kyiv mathematical festival 2019
Tags: Kyiv mathematical festival, combinatorics
10.05.2019 08:10
Umm... Using a greedy algorithm, it's easy to see that maximum is when the hatted dwarfs alternate except for one of them, so isn't the answer $48$?
17.12.2020 16:02
Answer is 33 Here is the solution .Let m be the number of dwarfs with hats . Let dwarfs be D1,D2,....,D99 We are looking indices at mod 99 İf Dk is dwarf with hat then D(k+50) and D(k+49) haven't hat.Because length between them are 48. Obviously for every Dk ,D(k+50) and D(k+49) are unique .There is no overlap. So at least 2m dwarfs with not hat then 99>= m+2m this implies 33>=m Now configuration for Dwarfs with hats are D3,D6,.....D99 (all 0 mod3) obviously there is no Dwarf with hat such that length between them is 48
17.12.2020 16:36
Kyiv Math Fest 2019 wrote: 99 dwarfs stand in a circle, some of them wear hats. There are no adjacent dwarfs in hats and no dwarfs in hats with exactly 48 dwarfs standing between them. What is the maximal possible number of dwarfs in hats? Easy. Numerate the dwarfs : $A_1, A_2, \dots, A_{99}$. Rearrange the order of dwarfs on the circle in the following greedy way . \[A_{1}, A_{50}, A_{99}, A_{49}, A_{98}, \dots, A_{2}, A_{51}\]it's easy to see at most $1$ dwarf among three adjacent dwarfs may be in a hat , which means there're at most $33$ dwarfs in hat , for the construction just take every third dwarf be in hat . $\textbf{Q.E.D.}$