MathDB
equivalent sequences

Source: Rioplatense 2017 L3 P6

October 19, 2022
combinatorics

Problem Statement

For each fixed positiver integer nn, n≥4n\geq 4 and PP an integer, let (P)n∈[1,n](P)_n \in [1, n] be the smallest positive residue of PP modulo nn. Two sequences a1,a2,…,aka_1, a_2, \dots, a_k and b1,b2,…,bkb_1, b_2, \dots, b_k with the terms in [1,n][1, n] are defined as equivalent, if there is tt positive integer, gcd(t,n)=1(t,n)=1, such that the sequence (ta1)n,…,(tak)n(ta_1)_n, \dots, (ta_k)_n is a permutation of b1,b2,…,bkb_1, b_2, \dots, b_k. Let α\alpha a sequence of size nn and your terms are in [1,n][1, n], such that each term appears hh times in the sequence α\alpha and 2h≥n2h\geq n. Show that α\alpha is equivalent to some sequence β\beta which contains a subsequence such that your size is(at most) equal to hh and your sum is exactly equal to nn.
Back to ProblemsView on AoPS