Let $n$ be a positive integer. The following $35$ multiplication are performed: $$1 \cdot n, 2 \cdot n, \dots, 35 \cdot n.$$Show that in at least one of these results the digit $7$ appears at least once.
Problem
Source: IberoAmerican 2023, Day 1, P1
Tags: number theory
13.09.2023 12:04
Ibero sometines features "grind" problems 1 or 4, this may be another case. I gave it not much thought, except to note that if $n$ ends in $1,3,9$ then $7n,9n,3n$ end in $7$, and $0$'s at the end of the decimal representation of $n$ may clearly be ignored. It thus suffices to prove that $2$-digit numbers of the form $a2,a4,a5,a6,a8$ where $a$ is a digit other than $7$ may be multiplied by one number in $\{1,2,\dots,35\}$ resulting in a number with $7$ in the tens digit. This is tedious but doable and may be shortened by considering many-factor numbers with $7$ in the tens digit such as $72,176,576$.
14.09.2023 17:58
I actually find this problem to be very good. Some people might say it's a bad problem because they spent 1 hour doing case work. But if you think smart, you can actually reduce to testing only 4 numbers (where 3 of them are trivial). This is the kind of problem that if you only want to solve p1 during the test, then you surely can test all the cases. But if you want to have time to solve problem 2 and 3, you better come up with a smart solution. I will write my full solution later today
19.09.2023 12:34
1- if n is odd then we are done . 2- if n is even considering that 35 number mod 100 , we are done with some case work ( such a bashy question but Im sure there exists a better way to solve this one
19.09.2023 15:13
I don't feel like thinking much about this, but just a small remark: $35$ is tight, from $n=2$. This in fact shows that any number that does not start with $1$ can be easily verified: some multiple will fall between $700...$ and $799....$. I'm not sure if there's a way to do it specifically for numbers starting with $1$.
20.09.2023 08:03
quote to gghx's comment The jury automatically awarded zero points to this kind of solution approach based on analyzing the most significant digits since there is a pathological case of the form n = 166...6 , as long as you want it to be . The only instance of digit 7 appears for n \cdot 33 = 549...978 . I leave to you the exercise of finding the decimal representation of k \cdot n for k \in \{1..35\} and asserting that there's no 7 digit elsewhere . p.s. I'm posting neither quote markup nor any LaTeX since I get an error message saying "new users may not post images"
20.09.2023 08:16
quote to M.rastgar I have provided a solution that breaks problem down into 5 cases 1. Numbers ending in 1,3,7,9 2. Numbers ending in 5 3. Numbers ending in 0 4. Even numbers with odd tens digit (4 "brute force" cases) 5. Even numbers with even tens digit (4 "brute force" cases) The details , well , solution is lengthy (+4 pages long) and it seems I may not write neither markup text nor links to external web site (/me new user ?) Official proposed solution considered 7 cases .
01.11.2023 08:28
If the units digit of $n$ is $1, 3, 7,$ or $9$, then $9n, n,$ and $3n$ respectively satisfy the condition. If the units digit of $n$ is $5$, then the remainders of $5n$ and $15n$ when divided by $100$ can only be $25$ or $75$. Obviously, they cannot both be $25$, because their difference $10n$ would then be divisible by $100$, which is not possible. Thus, one of them must have its last two digits as $75$. Therefore, all odd values of $n$ satisfy the condition. If $n$ is even, the problem can be simplified to proving that among the $2\cdot k, 4\cdot k, \cdots, 70\cdot k$ for any positive integer $k$, at least one of them contains the digit $7$. This is obvious and can be determined by considering the first digit of $k$.
27.07.2024 01:42
Did it mentally. Just consider 7 cases(5 are brute force) depending on the last digit of the number. The brute force cases, 2,4,6,8 and the not so brute force case 5, are subdivided by considering the second digit of the number. The argument works because you find out that we can always find a 7 in 1 of the last 2 digts of one of $n, 2n, \dots, 35n$. Then we just start trying to multiply the numbers in the cases we have times numbers between 1 and 35 until we find a 7 in the tens or ones. For 0, we have to prove the other cases first and then say, if 10 divdes n, we say $n = 10^a \cdot m$, with 10 not dividing m. Then, m ends in a non-0 digit and therefore there exists $k$ between 1 and 35 such that $km$ has a 7 digit. Since if we multiply $km$ by $10^a$ we only add zeros, then $kn$ still has a 7.
27.07.2024 02:11
Hancho6174 wrote: Did it mentally. Just consider 7 cases(5 are brute force) depending on the last digit of the number. The brute force cases, 2,4,6,8 and the not so brute force case 5, are subdivided by considering the second digit of the number. By the way did it in a total of 48 cases and subcases.
27.07.2024 15:30
Are you sure?
02.08.2024 05:57
Initially, I noticed by inspection that numbers ending in \(1, 3, 7, 9\) satisfy the condition because \(7 \cdot n, 9 \cdot n, 1 \cdot n, 3 \cdot n\) have a 7 in their last digit. However, I found the process to prove that numbers ending in \(2, 4, 5, 6, 8\) meet the condition to be quite cumbersome. After thinking about it for a while, I came up with this solution: To start, I demonstrated that for \(n \in {0, 1,2,3,4,5,6,7,8,9}\), the condition is satisfied. Let \(n = \overline{a_ka_{k-1}a_{k-2} \ldots a_0}\) It is known that \(\overline{a_ka_{k-1}} \cdot 10^{k-1} + 10^{k-1} > n \geq \overline{a_ka_{k-1}} \cdot 10^{k-1}\) Let \(a = \overline{a_ka_{k-1}}\) That is, \((a+1) \cdot 10^{k-1} > n \geq a \cdot 10^{k-1}\) **Case 1** In this case, we are considering \(a \geq 20\) Let \(w = \lceil{\frac{700}{a}}\rceil\) It is given that \(w\) is the smallest number such that \(700 \leq a \cdot w\) And since \(w \leq 35\) because \(a \geq 20\), then \(700 < (a+1) \cdot w < 800\) Because, if \((a+1) \cdot w > 800\), \(700 < a \cdot (w-1)\) Thus, \(800 > w \cdot (a+1) \cdot 10^{k-1} > w \cdot n \geq w \cdot a \cdot 10^{k-1} \geq 700\), so \(wn\) would have a 7 at least at the beginning. **Case 2** In this case, we are considering when \(a < 20\) Let \(w = \lceil{\frac{70}{a}}\rceil\) It is given that \(w\) is the smallest number such that \(70 \leq a \cdot w\) And since \(w \leq 3\) because \(a < 20\), then \(70 < (a+1) \cdot w < 80\) Because, if \((a+1) \cdot w > 80\), \(70 < a \cdot (w-1)\) Thus, \(80 > w \cdot (a+1) \cdot 10^{k-1} > w \cdot n \geq w \cdot a \cdot 10^{k-1} \geq 70\), so \(wn\) would have a 7 at least at the beginning.
08.08.2024 01:25
Matricy wrote: Are you sure? Yes