Prove that one can arrange all positive divisors of any given positive integer around a circle so that for any two neighboring numbers one is divisible by another.
Problem
Source: Kazakhstan NMO 2016, P1
Tags: number theory, national olympiad, 2016
17.03.2016 12:15
This problem is quite old. For instance, a special case can be found in the Ireland Team Training materials. So I come to a solution. This result trivially holds if the number, $n$, is a prime power, so assume otherwise. Now let $n =ap$ where $a,p$ are positive integers and $p$ is prime. We induct, assuming this result to be true for $a.$ Create the circle for $a$ and call it $\mathcal{C}.$ Further, by $k\mathcal{C}$ we denote the circle obtained by multiplying each entry of $\mathcal{C}$ by $k.$ Then, consider the two circles $\mathcal{C}$ and $p\mathcal{C}.$ Let $a,b$ be two successive entries in $\mathcal{C}.$ Then cut $\mathcal{C}$ in between $a,b$ and $p\mathcal{C}$ between $pa,pb.$ Now attach the two figures obtained so that $pa$ is joined to $a$ and $b$ is joined to $pb.$ Clearly this arrangement suffices by induction. We can choose the base case as any prime power, for which any arrangement holds. By induction, this result holds for all $n \in \mathbb{N}.$
29.05.2024 20:17
OTIS stronger version wrote: Let $n\geq 2$ be a positive integer. Prove that all divisors of $n$ can be written as a sequence $d_1,\dots,d_k$ such that for any $1\leq i<k$ one of $\frac{d_i}{d_{i+1}}$ and $\frac{d_{i+1}}{d_i}$ is a prime number. We can show that there is a bijection between finding a sequence of divisors and finding a path(from vertex to adjacent vertex) on an lattice $n$-dimensional hyperbox(on the coordinate plane) so that all lattice points are covered by the path. Note that vertex Here $n$ is the number of distinct prime divisors of the positive integer in question which we will call $\mathcal{P}$. Note that our hyperbox has dimensions $(e_1 + 1) \times (e_2 + 1) \times \dots \times (e_n + 1)$ where $\mathcal{P} = \prod_i^n p_i^{e_i}$. Note that point $(x_1, x_2, x_3, \dots, x_n)$ corresponds to $\prod_i^n x_i^{p_i}$. WLOG our path starts at the origin on the coordinate plane which corresponds to $1$ in terms of a divisors. We will use induction to prove this claim. Our base case of $n = 1$ is trivially true. Then we can easily induct upwards since we can connect our path between two $n-1$ hypercube graphs at the corners to form a block of $n-1$ hypercube graphs with length $e_n + 1$, so our induction is done.
28.08.2024 19:38
OTIS version We will prove it by using induction. $\textbf{Base case:}$ $n$-has only one prime factor $\iff n=p^{\alpha}$ then we can form the sequence as follows: $1,p,p^2, \dots , p^{\alpha}$. $\textbf{Inductive hypothesis:}$ Assume it's true for $n$-having $\ell$ prime factors. $\textbf{Inductive step:}$ Now we will prove that works for $n$ having $\ell+1$ prime factors. $\iff n=q^{\beta} \cdot t$ where $t$ has $\ell$ prime factors and let $a_1,a_2, \dots, a_k$ be the sequence of $t$. So now to prove that $n=q^{\beta} \cdot t$ works we form the sequence as follows: $a_1,a_2, \dots, a_k , q \cdot a_1, q \cdot a_2, \dots, q \cdot a_k \cdot q^2 \cdot a_1, q^2 \cdot a_2, \dots , q^2 \cdot a_k ,\cdots \cdots q^{\beta} \cdot a_1 , q^{\beta} \cdot a_2, \dots, q^{\beta} \cdot a_k.$ Hence we are done $\blacksquare$.
05.09.2024 17:06
The Otis version: Let the prime factorization of $n$ be $p^aq^br^c\dots$. Now, consider a coordinate lattice from $(1,1,1,...)$ to $(a,b,c,...)$ so that we have a one-to-one correspondence from factors of $n$ to points on the lattice. Notice that the given condition means that the lattice points corresponding to two adjacent terms of the sequence are adjacent themselves. Thus, the question is just asking if all such coordinate lattices have a Hamiltonian path. This is pretty easy induction on the dimension of the lattice.
11.11.2024 18:05
Otis version: Induction of the number of prime factors of n works
22.11.2024 04:22
We claim that there exists a sequence with either $d_1=1, d_k=n$ or $d_k=1, d_1=n.$ We show this by inducting on $\alpha,$ the number of prime factors that $n$ has. The base case is trivial. Now, suppose that our proposition holds for $\alpha=\ell$ for some positive integer $\ell.$ Then suppose $n$ has $\ell+1$ prime factors. Let $p$ be a prime factor of $n$ such that $v_p(n)=x.$ Also, let $n=p^xm.$ Then by our inductive hypothesis, there exists a sequence from $1$ to $m.$ Then, we can move to $mp,$ and using our inductive hypothesis again we can get to $p.$ Continuing, we will eventually end at either $p^x$ or $mp^x=n.$ (Visualize this as a path through lattice points in a $\ell$-dimensional space.) Hence, this provides a valid path, so we are done. QED