We call natural number $m$ ziba, iff every natural number $n$ with the condition $1\le n\le m$ can be shown as sum of [some of] positive and distinct divisors of $m$. Prove that infinitely ziba numbers in the form of $(k\in\mathbb{N})k^2+k+2022$ exist.
Problem
Source: Iran MO Third Round N3
Tags: number theory
08.09.2022 17:17
Hello, This is my solution:
08.09.2022 17:46
The only nice one in the contest ! Firstly , for each natural number $\alpha$ and odd $t \in \mathbb{N}$ such that $2^{\alpha}>t$ , number $n=2^{\alpha}t$ is "beautiful". Then by Henzel's lemma one can see that the equation $P(x)=x^2+x+2022 \equiv 0 \pmod {2^{\alpha}}$ has an integer root for each $\alpha$ and we can get that for this root $r_{\alpha}$ , we have $P(r_{\alpha})<2^{2 \alpha}$ and this number is beautiful. ( I'll post my full solution later )
08.09.2022 17:50
Shayan-TayefehIR wrote: The only nice one in the contest ! Firstly , for each natural number $\alpha$ and odd $t \in \mathbb{N}$ such that $2^{\alpha}>t$ , number $n=2^{\alpha}t$ is "beautiful". Then by Henzel's lemma one can see that the equation $P(x)=x^2+x+2022 \equiv 0 \pmod {2^{\alpha}}$ has an integer root for each $\alpha$ and we can get that for this root $r_{\alpha}$ , we have $P(r_{\alpha})<2^{2 \alpha}$ and this number is beautiful. ( I'll post my full solution later ) I posted your full solution.
08.09.2022 17:57
eser43 wrote: Shayan-TayefehIR wrote: The only nice one in the contest ! Firstly , for each natural number $\alpha$ and odd $t \in \mathbb{N}$ such that $2^{\alpha}>t$ , number $n=2^{\alpha}t$ is "beautiful". Then by Henzel's lemma one can see that the equation $P(x)=x^2+x+2022 \equiv 0 \pmod {2^{\alpha}}$ has an integer root for each $\alpha$ and we can get that for this root $r_{\alpha}$ , we have $P(r_{\alpha})<2^{2 \alpha}$ and this number is beautiful. ( I'll post my full solution later ) I posted your full solution. Not "full" actually
08.09.2022 17:59
Shayan-TayefehIR wrote: eser43 wrote: Shayan-TayefehIR wrote: The only nice one in the contest ! Firstly , for each natural number $\alpha$ and odd $t \in \mathbb{N}$ such that $2^{\alpha}>t$ , number $n=2^{\alpha}t$ is "beautiful". Then by Henzel's lemma one can see that the equation $P(x)=x^2+x+2022 \equiv 0 \pmod {2^{\alpha}}$ has an integer root for each $\alpha$ and we can get that for this root $r_{\alpha}$ , we have $P(r_{\alpha})<2^{2 \alpha}$ and this number is beautiful. ( I'll post my full solution later ) I posted your full solution. Not "full" actually
08.09.2022 18:15
Let $S$ be the set of "ziba" numbers. Lemma.$S$ is close under multiplication. Proof. Let $m,n \in S$ . Then consider the divisors $d_1,...,d_k$ of $n$. Consider the numbers $d_1m,...,d_km$ . Now we can produce $1 \leq l \leq n$ with some of $d_i$'s and so we can produce $lm$. Now consider a number $X$ between $lm,(l+1)m$. Since $X-lm$ can be written as sum of some distinct divisors of $m$ and clearly we're not using a number twice , we can produce $X$ and the lemma holds. Similarly , if $n \in S$ and $m/2 \le n$ , we can produce $mn$ Now let $x^2+x+2022 = f(x)$. Then $f(x+kf(x)) = k^2f(x)^2 + 2kxf(x) + f(x) + kf(x) = f(x)(k^2f(x)+2kx+k+1)$. Now let $f(x_0) \in S$ then it's enough to find $k$ such that : $f(x_0) \ge (k^2f(x_0)+2kx_0+k+1)/2$ which is true for $k=1$ . so it's enough to find one such $x$ which is ok.
04.10.2022 19:52
$\text{Lemma1:for all}$ nϵN, $\text{all natural numbers from 1 to}$$2^{n+1}-1$ $\text{can be written as the sum of some(one or more) distinct positive divisors of}$$2^{n}$ Proof:for any mϵN, $0<m<2^{n+1}$ the unique binary expression of m consists of at most n+1digits and each digit is either 0 or 1.if the t_th digit from right is 1,write$2^{t-1}$ and then, sum up all the written powers of 2.the sum is exactly m and all of the summands are positive divisors of $2^n$ so the lemma holds. Lemma2:If m be an odd natural number and nϵN such that $2^n\geq m$ then $2^n\cdot m$ is ziba Proof:The case m=1 holds hence all the numbers smaller than $2^{n+1}$ are writable in the desired way and $2^n\leq 2^{n+1}-1$ if and only if $2^n\geq 1$ which is true.if m>1Consider the sets A={$2^\alpha\cdot m$|$\alpha\leq n$,$\alpha$ϵZ} B={$2^\alpha$|$\alpha\leq n$,$\alpha$ϵZ} Now, $2^n\cdot m=2^n\cdot m$ and for any $0<k<2^n\cdot m$ there exists unique qϵN,rϵW such that k=mq+r and $q<2^n$ and $0\leq r\leq {m-1}$ According to Lemma 1, q can be written as the sum of some distinct elements of B so mq can be written as the sum of some distinct elements in A if r is nonzero; since r<m\leq{2^n} r can be written as the sum of some distinct elements of B and since A and B don't have any element in common(all of the elements of B are powers of2 and there is an odd prime which divides m(since m>1)and all elements of A) and all their elements are positive divisors of $2^n\cdot m$, lemma 2 is proved(if r=0 we are done after the first part) Now we prove that the equation $f(x)=x^2+x+2022=0$(mod$2^c$) has at least a solution for any $c\geq 2$,kϵN.We do so by induction on c.the base case c=2 holds because $f(0)=0$(mod4). Now suppose $f(x_0)=0$(mod $2^s$). It can be observed that $f(x_0+2^sh)=f(x_0)+2^sf'(h)$(mod $2^{s+1}$)which $f'(x)=2x+1$ and if $x_1=0(mod 2^s),x_1=0or 2^s(mod2^{s+1}$) so either $f(x_0)=0 or f(x_0+2^s)=0(mod2^{s+1})$ and the induction is complete. Suppose the contrary of the problem's claim,so there exists finitely many x so that $f(x)$ is ziba. Name them $r_1 ,r_2 ,...,r_t$. All the numbers $f(r_i)$ are finite so there exists a u such that $2^u>max{f(r_i)}$ and $u>11$.$f(x)=0(mod2^u)$has a root; so $f(x)=0(mod2^u)$ has a root in the set {0,1,2,...,$2^u-1$}like T and $f(0)\neq 0(mod2^u$).if $f(T)=2^\alpha\cdot v$ such that v is odd,we know $\alpha\geq u$. if $v\leq 2^\alpha$ ; $f(T)$ would be ziba two by lemma2, which is in contrast with the way T is chosen and the assumption that the problem's claim is wrong. if $v> 2^\alpha, 2^u\cdot (2^u+1)\leq 2^\alpha\cdot (2^\alpha+1)\leq f(x)\leq (2^u-1)^2+2^u+2021$ Which is again in contrast with $u>11$ so there are infinite natural values for x such that $f(x)$ is ziba and the problem is proved.