Prime-related integers [CMO 2018 - P3]

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Prime-related integers [CMO 2018 - P3]

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2018 Canadian Mathematical Olympiad - P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5452 posts

#1 h Mar 31, 2018, 2:16 AM • 4 Y

Y by Smita, Davi-8191, Adventure10, Mango247

Two positive integers $a$ and $b$ are prime-related if $a = pb$ or $b = pa$ for some prime $p$ . Find all positive integers $n$ , such that $n$ has at least three divisors, and all the divisors can be arranged without repetition in a circle so that any two adjacent divisors are prime-related.

Note that $1$ and $n$ are included as divisors.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

InCtrl

#2 h Mar 31, 2018, 3:12 AM • 5 Y

Y by Amir Hossein, UzbekMathematician, lneis1, Adventure10, Mango247

Solution

This post has been edited 4 times. Last edited by InCtrl, Mar 31, 2018, 3:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#3 h Mar 31, 2018, 4:12 AM • 2 Y

Y by Amir Hossein, Adventure10

solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

355 posts

#4 h Mar 31, 2018, 4:34 AM • 3 Y

Y by Amir Hossein, Adventure10, Mango247

Consider the graph with vertices as divisors and an edge between them if they are prime-related. We want to find a Hamiltonian cycle in this graph. If the nonzero exponents in the prime factorization of $n$ are $e_1,...,e_d$ , the graph is the unit distance graph on the lattice $\{0,1,...,e_1\}\times...\times\{0,...,e_d\}$ . When $n$ is a prime power, this is a line graph, so trivially there are no Hamiltonian cycles. If $n$ is a square, all $e_i$ are even, and thus the lattice has an odd number of points. But by coloring by the parity of the sum of coordinates, the graph is bipartite, and thus has no odd cycle (and thus no Hamiltonian cycle). Otherwise, some $e_i$ (WLOG $e_1$ ) is odd. Consider the lattice $\{0,...,e_2\}\times...\times\{0,...,e_d\}$ . By induction on the dimension one can easily see that this has a directed Hamiltonian path beginning at some point $O$ . Let the path without $O$ be $P$ and let the reverse of $P$ be $P'$ . Then traverse as follows: $\{0\}\times O\to\{0\}\times P\to\{1\}\times P'\to\{2\}\times P\to...\to\{e_1\}\times P'\to\{e_1\}\times O\to\{e_1-1\}\times O\to...\to\{0\}\times O$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

#5 h Apr 12, 2018, 1:41 AM • 4 Y

Y by jozuch, paccongnong19hy, Adventure10, Mango247

This is just a hamiltonian cycle in a grid-like graph. If $n$ is a power of a prime, then the graph is a line, so no cycle.

If $\tau(n)$ is odd, then coloring shows that there are no hamiltonian cycles.
If $\tau(n)$ is even, there is an even-length "side" in the graph, so it's easy to traverse the graph.
So the answer is non-square numbers that are not powers of a prime.

This post has been edited 1 time. Last edited by rkm0959, Apr 12, 2018, 1:41 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#6 h Aug 24, 2021, 12:48 AM

Y by

The answer is all $n$ which are not squares or powers of primes. Clearly powers of primes do not work, because 1 must also be adjacent to a non-prime. To show that all other numbers work, induct on the number of distinct prime factors of $n$ .

Base Case. It suffices to show numbers of the form $n=p^aq^b$ for $a, b$ not both even work. Consider a grid of squares shown below:

$\begin{tabular}{c||c|c|c|c|c|c} & $1$ & $p_1$ & $p_1^2$ & $p_1^3$ & $\cdots$ & $p_1^{k_1}$ \\ \hline \hline $1$ & 1 & $p_1$ & $p_1^2$ & $p_1^3$ & $\cdots$ & $p_1^{k_1}$ \\ \hline $p_2$ & $p_2$ & $p_1 p_2$ & $p_1^2p_2$ & $p_1^3p_2$ & $\cdots$ & $p_1^{k_1} p_2$ \\ \hline $p_2^2$ & $p_2^2$ & $p_1p_2^2$ & $p_1^2p_2^2$ & $p_1^3p_2^2$ & $\cdots$ & $p_1^{k_1} p_2^2$ \\ \hline $\vdots$ & $\vdots$& $\vdots$&$\vdots$ &$\vdots$ &$\vdots$ &$\vdots$ \\ \hline $p_2^{k_2}$ & $p_2^{k_2}$ & $p_2^{k_2} p_1$ & $p_2^{k_2} p_1^2$ & $p_2^{k_2} p_1^3$ & $\cdots$ & $p_1^{k_1} p_2^{k_2}$ \end{tabular}$
Constructing a circle satisfying the given conditions is equivalent to starting at 1, and moving through every single square in the grid, only travelling between consecutive entries every move. We claim that such a path is always possible if one of $k_1$ and $k_2$ is odd, and impossible if both $k_1$ and $k_2$ are even, which is equivalent to our base case.

First, we prove that such a path is impossible for $k_1, k_2$ both even. Color the squares of the $k_1+1$ by $k_2+1$ grid shown above black and white in an alternating fashion. Then at every step, we must move onto a square with different color than the square we started on. However, the number of black squares and white squares on the grid are not equal, because there are an odd number of total squares, while any valid path must pass through an equal number of black and white squares. Thus such a path is impossible.

Next, we provide a construction for one of $k_1, k_2$ odd. WLOG assume that $k_2$ is odd. Then begin at 1, travel down to $p_2^{k_2}$ directly, then travel to $n$ horizontally. Next, move up one step, then travel to $p_2^{k_2-1}p_1$ , and then move to $p_2^{k_2-2}p_1$ , and travel to $p_2^{k_2-2}p_1^{k_1}$ , and so on. Because $k_2$ is odd, our path will pass through $p_2^0p_1 = p_1$ , and thus we can return to $1$ , thus completing our cycle. This proves the base case.

Inductive Step. Assume that some number $n$ with $k$ distinct prime factors works. Then, we will show $n \cdot p_{i+1}^{k_{i+1}}$ for some $p_{i+1}$ not already a divisor of $n$ also works. First, arrange the divisors of $n$ in a valid configuration, which exists. Next, split the circle between any two numbers, thus creating a ``line". Since the circle has an even number of elements (because $n$ is not a perfect square), divide the resulting line into two parts down the middle.

Next, replicate the first half of the line and multiply each factor by $p_{i+1}$ . Moreover, if the element at one end of the line was $j$ , then connect $j \cdot p_{i+1}$ to the original line. Then, replicate the first half of the line again, in reverse order, then multiply each factor by $p_{i+1}^2$ . If the last element in the first half of the line was $x$ , then connect $x \cdot p_{i+1}$ to $x \cdot p_{i+1}^2$ . Next, replicate the first half and multiply by $p_{i+1}^3$ , and so on. More generally, if $r$ is even, then replicate the first half of the line in reverse order, multiply all the elements by $p_{i+1}^r$ , and connect it in that order to the truncated $p_{i+1}$ sequence. Once we get to the $k_{i+1}$ th replication, we split into cases:

$k_{i+1}$ is odd. Then, we can replicate the entire line in the same order as presented. After that, repeat the construction for the first half of the line, this time with the second half of the line, going down by a factor of $p_{i+1}$ every time, and reversing the order between alternating groups. Notice that the final group of the second half of the line with a factor of $p_{i+1}$ goes in the original order, and thus ends on $y \cdot p_{i+1}$ for some $y$ at the end of the second half of the line, which we can connect to the second half of the line, as desired.
$k_{i+1}$ is even. Then, the entire line is replicated in reverse order. Proceed similarly as in the first part; this time, the last group of the line with a factor of $p_{i+1}$ still ends at the same $y \cdot p_{i+1}$ (because an even number of iterations have passed since the $p_{i+1}^{k_{i+1}}$ block). Thus, we can still connect it to the second half of the line.

At this point, we have used all the factors of $n \cdot p_{i+1}^{k_{i+1}}$ in the circle, and our construction guarantees that any two adjacent divisors are prime-related. Thus the induction is complete.

Hence, all other positive integers $n$ must work, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

500 posts

#7 h Dec 28, 2021, 2:33 PM

Y by

We will prove that only if $n$ is a power of a prime or a square number does it not work.

It is easy to see that if $n$ is a power of a prime it doesn't work since there are no two primes that the 1 can border.

If $n=p_1^{e_1}p_2^{e_2}$ where $e_1\equiv e_2\equiv 0\pmod{2}$ then if we consider a 2d grid where the left side is labeled $\{ 1, p_1, p_1^2, \dots, p_1^{e_1} \}$ and the top side is labeled $\{ 1, p_2, p_2^2, \dots, p_2^{e_2} \}$ , if we color this grid white and black alternatively then since there are an odd number of grid cells, we reach the desired contradiction. Note that this argument can be extended to further dimensions.

We will now prove that all other $n$ work through an induction approach. For the base case consider when $n=p_1^{e_1}p_2^{e_2}$ where at least one of $e_1, e_2$ is even. We will use the same grid as before. In each grid cell we will write the corresponding $p_1^ap_2^b$ . It is easy to see that such a hamiltonian path exists in this grid.

Having our base cases covered, for the inductive step if we already have some $n'$ working with the sequence $d_1, d_2, \dots, d_k$ where $k$ is even, and we want to prove that some $n=p^an'$ works where $p$ is a prime, then notice that we can use the sequence
$\{ d_1, pd_1, p^2d_1, \dots, p^ad_1, p^ad_2, p^{a-1}d_2, \dots, pd_2, d_2, d_3, \dots, pd_k, d_k \}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

588 posts

#9 h Oct 13, 2022, 8:45 PM • 1 Y

Y by SatisfiedMagma

Very dirty problem,never hated evens so much

Canada 2018 #3 wrote:

Two positive integers $a$ and $b$ are prime-related if $a = pb$ or $b = pa$ for some prime $p$ . Find all positive integers $n$ , such that $n$ has at least three divisors, and all the divisors can be arranged without repetition in a circle so that any two adjacent divisors are prime-related.

Note that $1$ and $n$ are included as divisors.

Clearly $n$ cannot be a prime power because then on both sides of $1$ we must have a prime,but since $n$ is the perfect power of a prime this is not possible.

If $n$ is a perfect square.Then it has an odd number of factors.Define a move $\rightarrow$ as an operation which takes you from a term to its next term.Start from $1$ and note that after performing an odd number of $\rightarrow$ s we reach $1$ again.Now see that a $\rightarrow$ increases or decreases the power of exactly $1$ prime factor of the number on which it is performed at.So if we consider the sum of exponents of the primes in the prime factorisation of a number,we see that each $\rightarrow$ changes it parities.So if we start from $1$ and end at $1$ it will take an odd number of moves or the parity of the sum of the exponents changes an odd number of times and its actual parity is ultimately altered,which is a contradiction $\square$

So squares don't work either.

We claim that rest of the integers with atleast $3$ prime factors work.Here is solely inductive+constructive proof.Say $n=p^aq^b$ and WLOG assume $b$ is odd.We start of with this
$1,q,pq,p^2q,p^3q,\cdots,p^{a-1}q,q^2p^{a-1},q^2p^{a-2},\cdots,pq^2,q^2,q^3,q^3p,\cdots \text{ and so on}$ Clearly this maintain the conditions and if this analogy goes on until the end,the last string would start with $q^b$ as $b$ is odd and look like this
$q^b,q^bp,q^bp^2,\cdots ,q^bp^{a-1}$ And a total of $ab+1$ divisors have been covered forming a sequence which still satisfies our condition.Note that numbers of the form $p^i$ and $p^aq^j,1 \geq j \geq b$ are still left.So we attach the following string with the last string(or the previously constructed sequence)
$p^aq^b,p^aq^{b-1},...............,p^aq,p^a,p^{a-1},p^{a-2},...........,p$ And our base case for $n$ is constructed as $\frac{p}{1}=p$ $\square$
Inductive step : Assume that for $n=\prod_{i=1}^{k-1}p_i^{a_i}$ has a valid construction.
Call the terms of the construction $b_1,b_2,.....b_l$ where $l$ is the number of divisors of $n$ .Now we will prove that for $n'=\prod_{i=1}^{k+1}p_i^{a_i}$ has a solution too.The new prime is $p_k$ and its power is $a_{k+1}$ .Consider the sequence
$b_1,b_2,......,b_l,pb_l,p,b_{l-1},....,pb_3,pb_2,p^2b_2,p^2b_3,.....,p^2b_l...\text{ and so on}$ If $a_{k+1}$ is even the sequence ends with $p^{a_{k+1}}b_l$ and if $a_{k+1}$ is odd it will end with $p^{a_{k+1}}b_2$ .Nevertheless add this after the last term
$p^{a_{k+1}}b_1,p^{a_{k+1}-1}b_1,............,p^2b_1,pb_1$ Since by our inductive hypothesis $\frac{b_l}{b_1}=\frac{p^{a_{k+1}}b_l}{p^{a_{k+1}}b_1}$ is also prime,so there is no problem in $a_{k+1}$ being even.Thus our construction is achieved and every number which is not a square or a prime power works $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#10 h Nov 25, 2022, 7:22 PM • 3 Y

Y by centslordm, ike.chen, iamnotgentle

We wish to find a hamiltonian cycle in a graph where the divisors of $n$ are vertices and vertices are adjacent if they are prime-related. We claim all $n$ that are not perfect squares or powers of primes work.

Proof of necessity: Consider $n=p^k.$ If $k=0,1,$ then $n$ does not have enough divisors, and if $k\ge 2,$ then the cycle must be $1,p,p^2,\dots,p^k,1.$ Since $p^k$ is not prime, powers of primes do not work. Suppose $n=\prod p_i^{2\alpha_i}.$ Notice since $\tau(n)$ is odd, the cycle must have an odd length. Also, going from one divisor to an adjacent divisor either multiplies the divisor by one of $p_i$ or divides it by one of $p_i.$ Hence, after an odd number of moves, the original divisor will be multiplied by $\prod p_i^{\beta_i},$ where $\sum\beta_i$ is odd. This means that the final divisor cannot be the original divisor as at least one of $\beta_i$ is odd. Therefore, perfect squares do not work.

Proof of sufficiency: Let $n$ be of the form $\prod_{i=1}^k p_i^{\alpha_i}$ where $k\ge 2$ and at least one of $\alpha_i$ is odd. We proceed by induction on $k$ to show all such $n$ work. For the base case $k=2,$ assume WLOG that $\alpha_2$ is odd and the following construction works: $\begin{align*} 1,p_1,p_1^2\dots,p_1^{\alpha_1},\\ p_2p_1^{\alpha_1},p_2p_1^{\alpha_1-1},\dots,p_2p_1^2,p_2p_1^1,\\ p_2^2p_1,p_2^2p_1^2,\dots,p_2^2p_1^{\alpha_1},\\ p_2^3p_1^{\alpha_1},p_2^3p_1^{\alpha_1-1},\dots,\\ \dots,\\ p_2^{\alpha_2}p_1^{\alpha_1},p_2^{\alpha_2}p_1^{\alpha_1-1},\dots,p_2^{\alpha_2}p_1^1,\\ p_2^{\alpha_2},p_2^{\alpha_2-1},\dots,p_2^2,p_2,1, \end{align*}$ where we increase the exponent of $p_2$ every row while alternating increasing and decreasing the exponent of $p_1$ depending on the row. Notice the second to last row has the exponent of $p_1$ decreasing since $\alpha_2$ is odd. For our inductive step, assume all $n$ that satisfy our conditions with $k$ prime divisors work. Consider $n_{k+1}$ with $k+1\ge 3$ distinct prime divisors that satisfy our conditions and note we can let $n_{k+1}=n_kq^{\beta}$ where $q$ is a prime factor of $n_{k+1}$ and $2\nmid\beta.$ Since $n_k$ has $k$ prime divisors, we can move the divisors into the form $d_1,d_2,\dots,d_m,d_1$ such that adjacent divisors are prime-related. Then, for $n_{k+1},$ the following construction works: $\begin{align*} 1,d_1,d_2\dots,d_m,\\ qd_m,qd_{m-1},\dots,qd_2,qd_1,\\ q^2d_1,q^2d_2,\dots,q^2d_m,\\ q^3d_m,q^3d_{m-1},\dots,\\ \dots,\\ q^{\beta}d_m,q^{\beta}d_{m-1},\dots,q^{\beta}d_1,\\ q^{\beta},q^{\beta-1},\dots,q^2,q,1, \end{align*}$ since $\beta$ is odd, which makes the second to last row have the index of $d$ decreasing. Thus, our induction is complete. $\square$

This post has been edited 3 times. Last edited by Mogmog8, Nov 25, 2022, 8:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

279 posts

#11 h Feb 10, 2023, 5:23 PM • 1 Y

Y by mulberrykid

All $n$ such that $n$ is neither a perfect square nor a perfect power of a prime

Proof.
First we will prove that no prime powers work. FTSOC, assume such a configuration exists for $n=p^k$ for some prime $p$ and positive integer $k$ . Then obviously $1$ will be on that circle. To the left and right of $1$ , there must be a number each, but the only number prime-related to $1$ is $p$ itself, a contradiction.

Now we will prove that no perfect squares work. Let $n=p_1^{e_1}p_2^{e_2}\cdots{}p_k^{e_k}$ for primes $p_i$ and even positive integers $e_i$ . Consider the $n$ -dimensional hypercube in the $n$ dimensional coordinate system of side lengths $e_1$ , $e_2$ , $\cdots{}$ , $e_k$ with coordinates ranging from $(0,0,\cdots{},0)$ to $(e_1,e_2,\cdots{},e_k)$ . Let the point $(c_1,c_2,\cdots{},c_k)$ represent the number $p_1^{c_1}p_2^{c_2}\cdots{}p_k^{c_k}$ . Since if two numbers are prime-related, they will have exactly one coordinate differ by exactly $1$ , we see that if there is a placement of the coordinates around a circle satisfying the problem conditions, then there will be a "walk"(a "walk" is defined as a series of moves from point to point such that for each move, you move only one unit in one direction and you never end up at the same spot twice in this series of moves, with the exception of your last move) from $(0,0,\cdots{},0)$ to itself that visits every point in this hypercube. Since an even number of moves is required for such an action and there happen to be an odd number of points in this hypercube, it is impossible for such a walk to happen when $n$ is a perfect square.

Now we prove that all other numbers $n$ work. Taking the hypercube idea above, we may use the two-dimensional walk and generalize to $n$ dimensions using an inductive argument, thus proving that all non-square and non-perfect prime power numbers $n$ work and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2807 posts

#12 h Mar 13, 2023, 12:32 AM • 1 Y

Y by GeoKing

The answer is all $n$ that are not a perfect square and a power of a prime. The case where $n = p^e$ is quite obvious. For the perfect square note that it has an odd number of divisors, so we have to take an odd number of jumps to reach back to $1$ . But on each jump the exponent of the number differs by $1$ . Clearly this is a contradiction.

Now we prove that all other $n$ work using induction.

Base Case: Consider $n = p_1^{e_1}p_2^{e_2}$ . We can easily find a construction for this.

Inductive Step: Assume that there exists a construction for $k$ where the terms are $t_1, t_2, \dots t_j$ . We will show that $n = k \cdot p_i^{e_i}$ works. Consider the construction $t_1, t_2, \dots t_j, pt_j, pt_{j-1}, \dots, pt_2, p^2t_2, p^2t_3, \dots p^2t_j.$ This can be thought of as wrapping around a grid. So this is a valid construction and we are done.

This post has been edited 1 time. Last edited by coolmath_2018, Mar 13, 2023, 12:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

480 posts

#13 h May 10, 2023, 3:14 AM

Y by

Nice problem!

We claim that all positive integer $n$ that is not a power of a prime number and/or a perfect square works.

First if $n$ is a power of a prime, it is trivial to see that it doesn't work.

Then, if $n$ were to be a perfect square, there would be an odd number of factors $\rightarrow{}$ an odd number of move $\rightarrow{}$ which is impossible since there must be an even number of moves (starts at some configuration, ends at the same configuration).

Now consider the following: Let $a_{n}$ be the sequence of moves that starts from $1,0,0,...,0$ and ends with $0,0,...,0,1$ and $b_{n}$ be the opposite order of moves, where there are $n$ numbers in each. If we add another prime with an exponent of $q$ , we can construct a sequence of moves that looks like this:

$(0,0,...,0|0), (1,0,...,0|0) \rightarrow{}$ after $a_{n} \rightarrow{} (0,0,...,1|0), (0,0,...,1|1) \rightarrow{}$ after $b_{n} \rightarrow{} (1,0,...,0|1)$ ... until the last number is equal to $q$ and we have performed a sequence of $a_{n}$ or $b_{n}$ on it.

There are two possibilities: $(1,0,...,0|q)$ or $(0,0,...,1|q)$ . Either way, simply turn the digit 1 into a 0 and decrease the value of $q$ from then on.

Existence
If there are two prime factors and $n=p_{1}^{q_{1}}*p_{2}^{q_{2}}$ where $q_{1}, q_{2} \neq 0 \mod{2}$ . We claim that there is a configuration that satisfies problem conditions. Consider a graph with $0,1,...,q_{1}$ and $0,1,...,q_{2}$ as its axis values. Since at least one of them must be odd, we can simply "walk" down the respective odd axis and kind of make a snake-like pattern to reach (0,0) again.

Now that we have found existence, we are done. $\blacksquare{}$

motivation

This post has been edited 1 time. Last edited by Danielzh, May 10, 2023, 3:15 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5417 posts

#16 h Sep 13, 2023, 9:26 PM

Y by

Cute little geometry problem; Wikipedia courteously provided a diagram to get you started. Good luck!

Solution to Hamiltonian Path Version (Modified Kazakhstan 2016)

Attachments:

This post has been edited 2 times. Last edited by peace09, Sep 13, 2023, 9:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

315 posts

#17 h Dec 9, 2023, 3:47 PM

Y by

This problem reminds me of the Snake game!

We can prime factorize $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ such that $p_1 < p_2 \dots < p_k$ are distinct primes that divide $n$ . We claim that only $n$ such that there exists some integer $1 \le i \le k$ such that $e_i$ is odd and $k \ge 2$ .

To start us off, we can biject the set of divisors $d~|~n$ to a $k$ -dimensional box with dimensions $e_1, e_2, \dots e_k$ of lattice points using the function $f:\mathbb{R} \to \mathbb{R}^k$ where
$f(d) = \{\nu_{p_1}(d), \nu_{p_2}(d), \dots, \nu_{p_k}(d) \}$ We wish to prove there exists a Hamiltonian cycle in this graph. To quickly show that all $e_i$ cannot be even, we can "checkerboard-color" any vertex $(x_1, x_2, \dots, x_k)$ , black if $x_1 + x_2 + \dots + x_k$ is even, and white otherwise. Then any Hamiltonian cycle, every step we alternate colors, so there must be an equal number of white and black vertices in the graph. But the number of vertices $(e_1 + 1)(e_2 + 1) \dots (e_k + 1)$ is odd, contradiction. Additionally, if $k = 1$ , it is impossible for a cycle to exist without passing through a vertex again.

It suffices to demonstrate a construction for $k \ge 2$ and some $e_i$ odd, which we proceed with induction on $k$ . For $k = 2$ , without loss of generality assume $e_1$ is odd. Then move from the origin to $(0, e_2)$ , right to $(1, e_2)$ , down to $(1, 1)$ , right to $(2, 1)$ , then repeat the cycle of going up and down between $y = 1$ and $y = e_2$ until you hit $(e_1, 1)$ , go to $(e_1, 0)$ and finish at the origin.

Now suppose there exists a Hamiltonian cycle for $k = t$ . We can remove the origin, leaving us with a Hamiltonian path from a point $A$ to $B$ where $A, B$ are one unit from the origin. Let $K(\ell)$ be this Hamiltonian path translated $\ell$ units along the $t + 1$ -dimensional axis, and $K'(\ell)$ be the same path but from $B$ to $A$ . Suppose $O$ is the origin, and without loss of generality assume $e_1$ is odd. Then the cycle
$O \to K(0) \to K'(1) \to K(2) \to K'(3) \cdots \to K/K'(e_{t + 1}) \to (0, 0, \dots, e_{t + 1}) \to (0, 0, \dots, e_{t + 1} - 1) \cdots \to (0, 0, \dots, 1) \to O$ works. The induction is finished, thus our proof is complete.

This post has been edited 1 time. Last edited by blueprimes, Dec 9, 2023, 3:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1300 posts

#18 h Jan 30, 2025, 1:22 AM

Y by

Down we go:

We claim that the answer is all positive integers except powers of prime or perfect squares.
Clearly, perfect powers dont work.
Consider perfect squares. If there exists some valid construction for perfect squares, then, starting from $1$ , at each step, the parity sum of prime exponents changes at every move. Since it has odd number of divisors, we lead to contradiction.

Consider $n=p^aq^b$ , where at-least one of $a, b$ is odd. Notice that, thus there exists some Hamiltonian cycle on a $(a+1) \times (b+1)$ grid.
Now, consider inducting on the no of prime factors of $n$ . Consider the chain of numbers in circle $a_1 \cdots a_t$ for some $n$ with $p \nmid n$ .
Then for $p^k n$ , we have the construction and we are done: $a_1 a_1 p \cdots a_1 p^k p^k a_2 \cdots a_2 a_3 a_3 p \cdots \cdots$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

328 posts

#19 h Mar 26, 2025, 2:27 AM

Y by

It works for all numbers that aren’t perfect squares or prime powers

We begin with the construction.
We induct on the number of primes.
If $n = p^aq^b:$ first, assume $a$ is odd. Then, simply take:
$\begin{align*} 1\to p\to p^2 \to \dots \to p^a & \to p^aq \to p^aq^2 \to \dots p^a q^b \\ & \to p^{a - 1}q^b \to \dots \to p^{a - 1} q \\ & \to p^{a - 2} q \to \dots \\ & \vdots \\ & \to pq \to \dots \to pq^b \\ & \to q^b \to \dots \to 1 \end{align*}$ Then, to multiply upwards, assume that $(n, p) = 1,$ $n$ is achieved by $1, a_1, \dots, a_r\to 1,$ then to do $n\cdot p^a,$ simply take:
$\begin{align*} 1 \to p \to p^2\to\dots\to p^a & \to p^a a_1 \to \dots p^a a_r \\ & \to p^{a - 1}a_r \to \dots p^{a - 1} a_1 \\ & \vdots \\ & \to p a_k \to \dots \to p a_{\overline k} \\ & \to a_{\overline k} \to \dots \to a_k \to 1 \end{align*}$ where $k \in \{1, r\},$ dependent on the parity of $a$ (and $\overline k$ is the other one).

Now, we prove perfect squares can’t be achieved.
Observe that perfect squares have an odd number of factors. However, observe that for every consecutive pair, we have to “turn on” or “turn off“ a prime. This clearly gives us a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a