Source: 2018 Canadian Open Math Challenge Part C Problem 4 Given a positive integer $N$, Matt writes $N$ in decimal on a blackboard, without writing any of the leading 0s. Every minute he takes two consicutive digits, erases them, and replaces them with the last digit of their product. Any leading zeroes created this way are also erased. He repeats this process for as long as he likes. We call the positive integer $M$ obtainable from $N$ if starting from $N$, there is a finite sequence of moves that Matt can make to produce the number $M$. For example, 10 is obtainible from 251023 via \[2510\underline{23}\rightarrow\underline{25} 106\rightarrow 1\underline{06}\rightarrow 10\]$\text{(a)}$ Show that 2018 is obtainablefrom 2567777899. $\text{(b)}$ Find two positive integers $A$ and $B$ for which there is no positive integer $C$ (B.) such that both $A$ and $B$ are obtainablefrom $C$ $\text{(c)}$ Let $S$ be any finite set of positive integers, none of which contains the digit 5 (C.) in its decimal representation. Prove that there exists a positive integer $N$ (C.) for which all elements of $S$ are obtainable from $N$.
Problem
Source:
Tags: Comc, 2018 COMC
06.12.2018 17:07
06.12.2018 17:49
How do you solve c) ??
07.12.2018 05:48
@above try working backwards. First, find how to construct a N for a set of two numbers. Then, just use induction to prove that we can reach the N for the first k-1 numbers and the kth number. An outline: Step 1: Prove that if we can find a number N such that the last k digits of N can make the first number and N can make the second number, then we can always construct a number that works. This is obvious as adding an extra "10" to the beginning of N lets you cut out as many leading digits of N as you want. Step 2: Prove that if a number has a 0 and all digits after that 0 is the last k digits of the other number, then it is possible. This is true as we can add as many digits at the end of that 0 as we like and they can always be cut out by the zero. Thus, we can get the entire second number at the end of that 0, thus reducing the problem to step 1. Step 3: Prove that if a number has an even digit and all digits after that even digit is the last k digits of the other number, then it is possible. This is true as we can add $d_1$ followed by the remaining digits of the other number. combining these remaining digits will always give you a non-zero number, which we let to be $x$. Notice that as we cycle through all possible $d_1$, we can make $x*d_1$ any even number we want, no matter what the value of $x$ is (of course $x$ is not zero or 5). Then we can combine $d_1$ and the rest of the digits to make the desired even digit, thus reducing the problem to step 1. Step 4: Prove that if a number has an odd digit and all digits after that is the last k digits of the other number, then it is possible to reach either step 3,2, or 1. Reaching step 2,3 are essentially the same as reaching step 1. Reaching step 1 is the same as reaching step 2,3, except we don't stop at the first even digit. We can reach step 2,3 like this. First, we take the longest continuous substring of odd digits ending with the k+1th digit (the last k digits are matched already). Then, in the same manner as step 3, we can replace the odd digit with an odd digit $d_1$ followed by the longest continuous substring of odd digits of the second number. We can always choose a digit $d_1$ such that combining all these digits creates the original odd digit. Next, we may flip the two numbers. Thus, we now have an even digit to use step 3.