MathDB

5

Part of 2013 Swedish Mathematical Competition

Problems(1)

2^{n-3}n(n-1) n -tuples of integers fro 3 conditions

Source: 2013 Swedish Mathematical Competition p5

4/30/2021
Let n≥2n \geq 2 be a positive integer. Show that there are exactly 2n−3n(n−1)2^{n-3}n(n-1) nn-tuples of integers (a1,a2,…,an)(a_1,a_2,\dots,a_n), which satisfy the conditions: (i) a1=0a_1=0; (ii) for each mm, 2≤m≤n2 \leq m \leq n, there is an index in mm, 1≤im<m1 \leq i_m <m, such that ∣aim−am∣≤1\left|a_{i_m}-a_m\right|\leq 1; (iii) the nn-tuple (a1,a2,…,an)(a_1,a_2,\dots,a_n) contains exactly n−1n-1 different numbers.
combinatoricsinequalities