Editorial for DMOPC '21 Contest 4 P3 - Palindromic Presents

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: zhouzixiang2004

We give some possible constructions worth varying amounts of points.

Intuitively, we do not want any "carries" to occur when adding a subset of the palindromes, as it is much harder to ensure that the sum remains a palindrome after some carries. This encourages us to use many small digits in the construction. We would also like all our numbers (except for a $0$ ~0~) to have the same number of digits, so that the same digits "interact" with each other when adding up any subset. To avoid carries from the most significant digits, we can make all of them a $1$ ~1~. Trying to place some other digits on different place values, we might find a construction like:

0
11000000011
12000000021
10100000101
10200000201
10010001001
10020002001
10001010001
10002020001
10000100001

This and other constructions with $10^9 < S$ ~10^9 < S~ are given $20\%$ ~20\%~ of the points.

Note that we can have one number contain all $0$ ~0~'s between the least and most significant digits. Doing this, we might get something like:

This and other constructions with $10^8 < S < 10^9$ ~10^8 < S < 10^9~ are given $25\%$ ~25\%~ of the points.

We can use the digit $3$ ~3~ as well before $1+2+3+4$ ~1+2+3+4~ would result in a carry. Doing this, we might get something like:

This and other constructions with $10^6 < S < 10^7$ ~10^6 < S < 10^7~ are given $40\%$ ~40\%~ of the points. Constructions with $10^7 < S < 10^8$ ~10^7 < S < 10^8~ are given $30\%$ ~30\%~ of the points.

To do better than $7$ ~7~ digits for each number, we need to consider numbers with more than $4$ ~4~ nonzero digits. As we need the $9$ ~9~ nonzero numbers in our set to be distinct while using small digits, we might try representing numbers in base $3$ ~3~, giving something like:

This construction works perfectly, as $10-1 = 9$ ~10-1 = 9~ happens to be a power of $3$ ~3~, giving $S = 99999$ ~S = 99999~ with no carries. This and other constructions with $S = 99999$ ~S = 99999~ are given $70\%$ ~70\%~ of the points. Constructions with $10^5 < S < 10^6$ ~10^5 < S < 10^6~ are given $60\%$ ~60\%~ of the points.

To optimize further, we might try using the digit $3$ ~3~ as well to give us more freedom to choose the numbers. Trying some combinations of numbers, we might find:

With $S = 99899$ ~S = 99899~. This is given $90\%$ ~90\%~ of the points.

As we want to minimize the more significant digits, we can swap the thousands and hundreds digits of everything to get:

With $S = 98989$ ~S = 98989~. This turns out to be the minimum possible $S$ ~S~ and is given $100\%$ ~100\%~ of the points.

Remark 1: We can verify using recursive backtracking that it is impossible to obtain a smaller $S$ ~S~. In fact, another way to approach this problem is to write a recursive backtracking program to help find the construction above for us.

Remark 2: The above construction with $S = 98989$ ~S = 98989~ is unique, up to reordering the elements.

Remark 3: We can prove that there does not exist a set of $11$ ~11~ or more non-negative integers with this property by showing that some subset of the $\ge 10$ ~\ge 10~ nonzero numbers (say $a_1, a_2, \dots, a_{10}$ ~a_1, a_2, \dots, a_{10}~) will sum to a multiple of $10$ ~10~. This claim follows from that some two of the $11$ ~11~ prefix sums $0, a_1, a_1+a_2, \dots, a_1+a_2+\dots+a_{10}$ are the same modulo $10$ ~10~ by Pigeonhole, so their difference corresponds to a subset that sums to a multiple of $10$ ~10~.

Comments

There are no comments at the moment.