For every permutation $ \tau$ of $ 1, 2, \ldots, 10$, $ \tau = (x_1, x_2, \ldots, x_{10})$, define $ S(\tau) = \sum_{k = 1}^{10} |2x_k - 3x_{k - 1}|$. Let $ x_{11} = x_1$. Find I. The maximum and minimum values of $ S(\tau)$. II. The number of $ \tau$ which lets $ S(\tau)$ attain its maximum. III. The number of $ \tau$ which lets $ S(\tau)$ attain its minimum.
Problem
Source: China TST 1999, problem 6
Tags: combinatorics unsolved, combinatorics
zhaoli
26.06.2005 10:52
The Chinese version of this problem state: $\displaystyle S(\tau) = \sum_{k = 1}^{10} |2x_k - 3x_{k + 1}| $ But I think, it is the same meaning.
mumath
04.02.2006 05:10
min S=45 and there are 36 permutations Max S=125and there are 720 permutations
math10
26.08.2008 04:59
solution?help me.
KDS
10.07.2009 11:13
This problem is nice but I cannot solve.Can any of you post a solution or give me some hints,please?Thank you very much.
soryn
01.10.2024 23:58
Who can solve this problem?
CatinoBarbaraCombinatoric
15.10.2024 09:37
min S=57 Using triangolar inequality we have S≥55 but if we want S=55 we need 3x_(n-1)>=2x_n for every n but when x_(n-1)=1 It cannot be possibile. So S≥56 but S Is odd so S≥57. S=57 is achievable by (1,2,3...,10) Assume WLOG x_1=1 S=57 if and only if 3x_(n-1)>=2x_n for every n≠2 and x_2=2 ( because the number following 1 must be 2). Now this mean 2x_3≤6 so x_3=3; x_4=4; x_5=5 or 6. If x_5=5 x_6=6 or 7. If x_6=6 the other numbers can be put in every order we the only condition that x_7≠10 so we have 3×3×2=18 possibilities. If x_6=7 we have ti put the remaing numbers such that 10 is not immediately after 6 so there are 3×2×2+3×2=18 possibilities. If x_5=6 then we have to put the remaing numbers such that x_6≠10 and 5 is followed by 7 or is the last number. So 3×3×2+3×3×2=36 possibilities. So the Total number of possibilities with x_1=1 are 18+18+36=72 and the total number of permutations that minimize S is 720.