MathDB
Operation on 10 tuple with sum 2019

Source: China TST 2019 Test 2 Day 1 Q2

March 16, 2019
combinatoricsalgorithms

Problem Statement

Let SS be the set of 1010-tuples of non-negative integers that have sum 20192019. For any tuple in SS, if one of the numbers in the tuple is ≥9\geq 9, then we can subtract 99 from it, and add 11 to the remaining numbers in the tuple. Call thus one operation. If for A,B∈SA,B\in S we can get from AA to BB in finitely many operations, then denote A→BA\rightarrow B.
(1) Find the smallest integer kk, such that if the minimum number in A,B∈SA,B\in S respectively are both ≥k\geq k, then A→BA\rightarrow B implies B→AB\rightarrow A.
(2) For the kk obtained in (1), how many tuples can we pick from SS, such that any two of these tuples A,BA,B that are distinct, A↛BA\not\rightarrow B.
Back to ProblemsView on AoPS