Let $K$ be an odd number st $S_2{(K)} = 2$ and let $ab=K$ where $a,b$ are positive integers. Show that if $a,b>1$ and $l,m >2$ are positive integers st:$S_2{(a)} < l$ and $S_2{(b)} < m$ then : $$K \leq 2^{lm-6} +1$$($S_2{(n)}$ is the sum of digits of $n$ written in base 2)
Problem
Source: Iran MO 3rd round 2023 , NT exam , P3
Tags: number theory
18.08.2023 21:14
Bump, any solution? Also, if the other exams have been held, can you post the problems from them as well?
18.08.2023 21:33
@above this is probably the best and hardest problem in the exams so far and if you wanna know one idea is to write $a,b$ in the form $a = \sum 2^{a_i}$ and bound the cardinality of the set $A+B$ where $A=\{a_1,...,a_{l-1}\}$ and $B=\{b_1,...,b_{m-1}\}$(where obviously $a_{l-1}=b_{m-1}=0$) and forgive me for not posting the full sol I'm on mobile rn And I'll post the rest of problems whenever they're published.
20.08.2023 18:21
Ooo no, Holy Jesus; an amazing NT problem after a while proposed in the contest. A warm congrats to the proposer and a jealous to whom participated in the test! Enjoy this beauty guys!
22.08.2023 05:27
To be very frank, the solution felt very underwhelming to me, much because at some point the solution just _ends_. I will elaborate on this later. We first rephrase the problem as follows: Let $K=2^x+1$, such that $x \in \mathbb{Z}^+$. Let $K=ab$, such that $a,b \neq 1$. Show that: $$ K \le 2^{(s_2(a)+1)(s_2(b)+1)-6} + 1 $$where $s_2(n)$ is the sum of digits of $n$ written in base 2. For one, as $K=2^x+1$ we may reduce the problem statement to: $$ x \le (s_2(a)+1)(s_2(b)+1)-6 $$ As per #3, we shall also define: $$ a = \sum_{i=0}^{|A|}2^{a_i}, \; b = \sum_{j=0}^{|B|}2^{b_j} $$Let $A = \{a_i\}_{i=0}$, $B = \{b_j\}_{j=0}$, and $\{a_i\}$ and $\{b_i\}$ are in ascending order. Trivially, we must have $a_0=b_0=0$. Lemma 1: Consider the _multiset_ $A+B=\{a_i+b_j|a_i \in A, \; b_j \in B\}$. Now $\sum_{l \in A+B}2^{l} = K = 1 + 2^x$ Proof: Trivial as $ab=K$ $\square$ Lemma 2: $a_1 = b_1$. Proof: Note that by Lemma 1, $\sum_{l \in A+B}2^{l} = 1 + 2^x$. In other words, if we are allowed to combine 2 of the same element $x \in A+B$ into a single $x+1$, then we should be able to change the multiset $A+B$ into $\{0,x\}$. But considering the smallest values in $A+B$, these must include $\{1, a_1, b_1\}$. As all values in $\{a_i\}$ and $\{b_i\}$ are distinct though, the only way that this is possible is for $a_1 = b_1$. $\square$ Let us set $\alpha = a_1 = b_1$. Lemma 3: $|A||B| \ge x - \alpha + 2$ Proof: We note that $|A||B| = |A+B|$. Recall the process described in Lemma 2 about "combining values". Now, to "combine" the values in $A+B$ to form a single $x$, we should be able to "combine" some values (or maybe none!) to form the set $\{1, \alpha, \alpha, \alpha +1, \alpha +2, \cdots, x-1\}$, which is necessary to "combine" the 2 $\alpha$ in $A+B$ to form an $x$. But this set has size $x-\alpha +2$. $\square$ Lemma 4: Let us write $a = m_a 2^{\alpha} + 1, \; b = m_b 2^{\alpha} + 1$. Then, $m_a + m_b$ is a multiple of $2^{\alpha}$. Proof: As $$ K = 2^x+1 = ab = m_am_b2^{2\alpha} + (m_a+m_b)2^{\alpha} +1 $$we must then have: $$ 2^{x-\alpha} = m_am_b2^{\alpha} + (m_a+m_b) $$Considering mod $2^{\alpha}$, we are done. $\square$ Lemma 5: $|A|+|B| \ge \alpha +3$ But as $\alpha \in A,B$, $m_a$ and $m_b$ must be odd. Then, $\{1, 1, \alpha, \alpha, \alpha +1, \alpha +2, \cdots, 2\alpha -1\}$ is a subset of the multiset $A \cup B$. The conclusion follows. $\square$ Lemma 6: $x \le (|A|+1)(|B|+1)-6$ Proof: Combining Lemmas 3 and 5, note that: $$ |A||B| + (|A| + |B|) + 1 \ge (x- \alpha +2) + (\alpha + 3) + 1 = x+6 $$ The proof is complete. $\blacksquare$ To me, the problem seemed like it has a lot more potential. Looking at Lemma 4, it seems likely that a quantification of the solution is possible, though I lack the technical competency to come close to it. This has the potential to lead to a quantifications of all such equality cases. Alas, the problem did not ask for it, hence I did not provide it. The proof also seems quite long, though only for technicalities. It does not really have many ideas, and felt underwhelming, though I may be looking at the wrong source if I am looking for harder questions.
22.08.2023 07:41
@above indeed this problems didn't require combining some new ideas and it was more about technicality and bashing.I said this was the hardest problem in the exams and actually I was quiet right I guess, since the other problems where a bit easier imo(or at this order) But if you wanna challenge yourself , go solve P2 of NT exam.Have fun:)