Let $(x_1,x_2,\dots,x_{100})$ be a permutation of $(1,2,...,100)$. Define $$S = \{m \mid m\text{ is the median of }\{x_i, x_{i+1}, x_{i+2}\}\text{ for some }i\}.$$Determine the minimum possible value of the sum of all elements of $S$.
Problem
Source: 2018 Thailand TST 4.2
Tags: number theory
CHN_Lucas
22.11.2022 10:42
Interesting problem.
$2+4+\cdots+66+67=1189$
@above. BTW, anyone with sol to the generalized situation?$(100\rightarrow n)$
MathLover_ZJ
22.11.2022 15:27
CHN_Lucas wrote: Interesting problem.
$2+4+\cdots+66+67=1189$
@above. BTW, anyone with sol to the generalized situation?$(100\rightarrow n)$ not really. for example,\[100,2,1,99,4,3,98,6,5,\cdots,68,66,65,67\]
AFOD
22.11.2022 15:58
But 67 is the median of {65,67,100},so I think the answer is 1189
MathLover_ZJ
22.11.2022 16:06
but the problem does not define $x_{101}=x_1,x_{102}=x_2$,so I think $1\leq i\leq 98$.
AFOD
22.11.2022 16:33
If so then 1122 is right.But I prefer the circle than the line.
CHN_Lucas
23.11.2022 07:45
The original problem meant the circle actually. Anyway, the generalized situation seemed harder and more challenging.
KhongMinh
23.11.2022 15:15
Quidditch wrote: Let $(x_1,x_2,\dots,x_{100})$ be a permutation of $(1,2,...,100)$. Define $$S = \{m \mid m\text{ is the median of }\{x_i, x_{i+1}, x_{i+2}\}\text{ for some }i\}.$$Determine the minimum possible value of the sum of all elements of $S$. The problem meant line. We can generalized for $n=3k+1$
Define that
$m_i$ is the median of $\{x_{3i-2},x_{3i-1},x_{3i}\}$ for $i=1,...,33$.
$n_i$ is the min of $\{x_{3i-2},x_{3i-1},x_{3i}\}$ for $i=1,...,33$.
We have:
$\sum m_i>\sum n_i$
$\implies \sum m_i\ge\sum n_i+33\implies \sum 2m_i\ge \sum m_i+\sum n_i+33\ge 1+2+...+66+33=2244\implies \sum m_i\ge 1122$
Construct:
$A=\{1,3,5,...,65\}$
$B=\{2,4,...,66\}$
$C=\{67,68,...,100\}$
For example: $C,B,A,C,B,A,...,C,B,A,C$
In position $A,B,C$ pick a number in $A,B,C$