Let $n$ be a positive integer, which gives remainder $4$ of dividing by $8$. Numbers $1 = k_1 < k_2 < ... < k_m = n$ are all positive diivisors of $n$. Show that if $i \in \{ 1, 2, ..., m - 1 \}$ isn't divisible by $3$, then $k_{i + 1} \le 2k_{i}$.
Problem
Source: 69 Polish MO 2018 Second Round - Problem 2
Tags: number theory, combinatorics, Divisors, Poland, inequalities
28.04.2018 20:40
Hint: Suppose all odd divisors of $n$ are $x_1,x_2,...,x_l$. Then it is clear that $k_1=1,k_2=2,k_3 \le 4, k_4 \le x_1, k_5 \le 2x_1,k_6 \le 4x_1,...$
28.04.2018 20:41
Call $(x, 2x, 4x)$ a triple such that $x$ is a positive integer. Note that because $v_2(n)=2$, ${k_j}$ can be written as the disjoint union of some triples. If $i$ is not divisible by three, then since each triple contains three elements, there exists at least one triple that contains values both greater than and less than $k_i$. This means $k_i$ lies between either $x$ and $2x$ or $2x$ and $4x$, where $x$ is an odd element of ${k_j}$, from which the result is clear.
28.04.2018 20:55
mruczek wrote: Let $n$ be a positive integer, which gives remainder $4$ of dividing by $8$. Numbers $1 = k_1 < k_2 < ... < k_m = n$ are all positive diivisors of $n$. Show that if $i \in \{ 1, 2, ..., m - 1 \}$ isn't divisible by $3$, then $k_{i + 1} \le 2k_{i}$. Assume the contrary then $k_{i+1}>2k_{i}>k_{i}$
28.04.2018 22:38
This problem was proposed by Burii.