divisors on a circle

The post below has been deleted. Click to close.

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

Valentin Vornicu

7301 posts

Valentin Vornicu

#1 h Apr 21, 2005, 6:40 AM • 8 Y

Y by harazi, Adventure10, jhu08, HWenslawski, ImSh95, Mango247, cookie130, ItsBesi

Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

Z K Y

The post below has been deleted. Click to close.

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

Myth

4464 posts

Myth

#2 h Apr 21, 2005, 7:09 AM • 9 Y

Y by vsathiam, lneis1, Adventure10, jhu08, HWenslawski, ImSh95, Mango247, cookie130, ld414think

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

Ravi B

3083 posts

Ravi B

#3 h Apr 23, 2005, 9:39 AM • 11 Y

Y by mijail, Adventure10, jhu08, thedragon01, starchan, CyclicISLscelesTrapezoid, ImSh95, Ritwin, bobthegod78, Mango247, cookie130

Here is my candidate for the solution with the most overkill. We will use the following results from graph theory.

Dirac's Condition: Let $G$ be a graph with $v \ge 3$ vertices. If every vertex has degree at least $\frac{v}{2}$ , then $G$ has a Hamiltonian cycle.

Chvatal's Condition: Let $G$ be a graph with $v$ vertices ( $v$ odd). If every vertex has degree at least $\frac{v-1}{2}$ , and at most $\frac{v-1}{2}$ vertices have degree exactly $\frac{v-1}{2}$ , then $G$ has a Hamiltonian cycle.

We can check that the divisor graph obeys one of these two conditions, provided that $n$ is not the product of two distinct primes.

Can you find a solution with more overkill?

This post has been edited 1 time. Last edited by Ravi B, Apr 23, 2005, 1:25 PM

Z K Y

The post below has been deleted. Click to close.

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

Myth

4464 posts

Myth

#4 h Apr 23, 2005, 9:51 AM • 4 Y

Y by Adventure10, jhu08, ImSh95, Mango247

He-he. In another thread rrusczyk wrote that convex hull and discrete continuity are too complicated ideas...
Your idea with Hamiltonian graph is absolurely right and clear. It was my first idea too. I always have in my mind this nice theorem.

Z K Y

The post below has been deleted. Click to close.

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

brothers-brt

32 posts

brothers-brt

#5 h Nov 20, 2012, 5:42 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

an easy one
we proof by induction
we only need to proof that if n is an int and p is a prime and it's true for n it's true for N*p

Z K Y

The post below has been deleted. Click to close.

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

brothers-brt

32 posts

brothers-brt

#6 h Nov 20, 2012, 5:44 PM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, and 1 other user

some thing else how can I get some of those stars !!!!!!!

Z K Y

The post below has been deleted. Click to close.

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

Abdollahpour

63 posts

Abdollahpour

#9 h Jul 2, 2017, 12:20 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

$n=p^k is the answer$

This post has been edited 2 times. Last edited by Abdollahpour, Jul 2, 2017, 4:16 PM

Z K Y

The post below has been deleted. Click to close.

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

franchester

1487 posts

franchester

#10 h Jan 5, 2020, 3:53 AM • 4 Y

Y by AlastorMoody, jhu08, ImSh95, Adventure10

I claim that all composites except for numbers of the form $pq$ work, where $p$ and $q$ are distinct primes. It is easy to see that $pq$ fails, and that numbers of the form $p^k$ work.

I will now show that all numbers of the form $p^aq^b$ work for all pairs of $a$ and $b$ except for when they are both one. We first isolate the factors of the form $p^k$ , and place them such that $p$ and $p^a$ are adjacent. Now, "split" open this circle and place $pq$ next to $p$ and $p^aq$ next to $p^a$ . Since the numbers left all have some factor of $q$ , they are all not pairwise prime, so "closing" the circle with these numbers yields a valid construction.

I now show that numbers with $\geq 3$ primes work. For the three primes, take the previous construction, and split the circle open at $p$ and $pq$ . Note that all the numbers we have left to place have some factor of the third prime $r$ , so we can simply place $pqr$ next to $pq$ and $pr$ next to $p$ to achieve a valid construction. Now we can see that we can achieve four primes in a similar fashion: split at $p$ and $pr$ , and suppose the fourth prime is $s$ . We can place $ps$ next to $p$ and $prs$ next to $pr$ and place all factors that are divisible by $s$ . This can clearly be extended to an indefinite number of primes, so we are done.

This post has been edited 1 time. Last edited by franchester, Jan 5, 2020, 3:53 AM

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#11 h Jul 7, 2020, 1:32 AM • 6 Y

Y by naman12, jhu08, Quidditch, Mango247, Mango247, Mango247

We claim that such an arrangement is possible iff $n$ is not the product of two distinct primes. First, we show that such an arrangement is impossible in the latter case; let $n=pq$ , then the divisors of $n$ greater than $1$ are $p,q,pq$ , but $p$ must be next to $q$ in any such circle, contradiction.

Now, we show that such an ordering is possible for any other $n$ . First, in the case that $n=p^k$ for some prime $p$ and integer $k\ge 2$ , note that any ordering works. Additionally, remark that in the case $n=pqr$ for some primes $p,q,r$ , we can take the ordering $\{p,pq,q,qr,r,rp,pqr\}$ .

In the case that $n$ is square-free, either we can use the construction for $n=pqr$ , or $n$ has at least four prime divisors and we can take some prime divisor $p\mid n$ , then take the construction for $n/p$ , choose two adjacent elements $a,b$ in that construction, then insert the multiples of $p$ in some consecutive order with $ap$ next to $a$ and $bp$ next to $b$ . Similarly, in the case that $n$ is not square-free, choose a prime $p\mid n$ such that $n/p$ is not square-free and insert multiples of $p$ similarly to before, or $n=p^k$ and we have already found the construction thereof.

At least one of the criteria $\exists p\mid n \mbox{ s.t. } p^2\mid n$ , $\exists p\ne q\ne r\ne p \mbox{ s.t. } pqr\mid n$ must hold as long as $n$ is not the product of exactly two distinct primes, hence 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.

Archimedes15

1491 posts

Archimedes15

#12 h Aug 25, 2020, 5:33 PM • 4 Y

Y by jhu08, ImSh95, Mango247, Mango247

Claim: We can create such a circle for all composite numbers other than numbers of the form $n = pq$ where $p,q$ are distinct primes.

If $n = pq$ with $p,q$ distinct primes, the three divisors that are greater than $1$ are $p, q, pq$ . Obviously they do not meet the condition as $p,q$ are forced to be next to each other, and they are relatively prime to each other.

There are a few cases we have to look at. The first case is if $n = p^k$ where $k \geq 2$ . Obviously, all numbers of this form must satisfy the condition as all divisors $>1$ are multiples of $p$ .

The next case we have to look at is $p^aq^b$ with $a,b \geq 2$ . Notice that all of the terms with the exception of the powers of $p$ and $q$ must share a common divisor as they contain powers of both $p$ and $q$ . So, start with a circle of the divisors of $p^aq^b$ other than 1 and the powers of $p,q$ . All of these divisors have both powers of $p$ and $q$ . If you place all of the powers of $p$ between one pair of terms and all of the powers of $q$ between another pair of terms, you have a circle that satisfies the conditions. So, you can do it for this case as well.

Another case to consider is the case where we have $pq^n$ with $n \geq 2$ . Note that all of the divisors other than $1$ and $p$ have a power of $q$ in them. So, you can place all of the divisors greater than $1$ except for $p$ into a circle in such a way that there is at least one pair of adjacent numbers that are multiples of $p$ and place the $p$ in between that pair of adjacent numbers. So, it is possible for this case as well.

There is one last case to consider, which is $n = p_1^ap_2^bp_3^c\ldots$ where $a,b,c,\ldots \geq 1$ . First, we can start by creating a circle that contains the integers $p_1p_2,p_2,p_3,\ldots,p_np_1$ . All multiples of $p_1$ go in between $p_np_1$ and $p_1p_2$ and so on with multiples of $p_k$ going between $p_{k-1}p_k$ and $p_kp_{k+1}$ . So, it is also possible to create such a circle for this case.

As all of the cases have been addressed, it has been proven that you can create such a circle for all composite numbers other than $n=pq$ with $p,q$ distinct primes.

This post has been edited 1 time. Last edited by Archimedes15, Aug 25, 2020, 5:43 PM
Reason: added newline to make aesthetically pleasing

Z K Y

The post below has been deleted. Click to close.

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

EulersTurban

386 posts

EulersTurban

#13 h Aug 26, 2020, 3:46 PM • 2 Y

Y by jhu08, ImSh95

First we shall show that for all numbers $n=p_1p_2p_3\dots p_k$ there is a possible arrangment, where $k \geq 3$ .

We define a $p_i$ -sector to be a circle section of angle $\alpha$ where all the numbers that are on the circumference of the circle are divisible by $p_i$ .
We firstly throw on the numbers $p_i$ and $p_ip_{i+1}$ onto the circle for all $i$ , where $1 \leq i \leq k$ and where all the indexes are taken $\text{mod}\; k$ .

Now we devise the following algorithm:
The algorithm:
We start by taking the $p_1$ sector, and we place all the numbers divisible by $p_1$ and who divide $n$ , into the $p_1$ sector and we place this between $p_1$ and $p_1p_2$ , now we do this for the $p_2$ sector, then for $p_3$ , etc...
When this is done we take a look at the repeating numbers and delete one of that number until we have just one of that number on the circle.

By this way every single divisor is on the circle and the neighboring condition is satisfied.Because we have that in the $p_i$ -sector the $GCD$ is equal to at least $p_i$ .

Now we shall show that it is possible for $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ , where $k \geq 3$
We still use our algorithm but this time when we encounter a number of the form $p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$ we take a look at the exponents.
Now if we have let's say number $d$ , where $d \mid n$ , depending on the exponent we place $d$ in the $p_i$ sector, if we have that $v_{p_i}(d) \geq v_{p_j}(d)$ for all $j$ , where $1 \leq i,j \leq k$ .
Now again we delete until we are left with just one of $d$ .

Now we take a look at trivial $n=p^{\alpha}$ , where $\alpha > 1$ .This is an easy construction. We just place $p^i$ , in ascending order on the circle, where $k \geq i > 0$ .

Now we look at $n=p^{\alpha}q^{\beta}$ .
Obviously when $n=pq$ this is impossible.
So let's assume $WLOG$ that $\alpha \geq \beta$ .
We start off with the construction for $p^2q$ .We place the numbers in the following order: $p,p^2,p^2q,q,pq$ onto the circle.
Again we divide into the $p$ sector and $q$ sector. We now use our algorithm with the divisor types $p^{\gamma}q^{\delta}$ to generalize for $p^{\alpha}q^{\beta}$ .

Thus giving us the answer of $n \in \mathbb{N} \backslash (\mathbb{P} \cup \{1\} \cup \{pq \mid p\neq q;p,q\in \mathbb{P}\})$ ,where $\mathbb{P}$ is the set of primes.
In other words the only solutions are all composite numbers except of the form $n=pq$ , where $p,q$ are distinct primes

Z K Y

The post below has been deleted. Click to close.

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

brianzjk

1201 posts

brianzjk

#14 h Aug 29, 2020, 3:01 AM • 2 Y

Y by jhu08, ImSh95

We claim that all composite numbers not in the form of $pq$ work, where $p$ and $q$ are primes.

We have several cases.
It is easy to see that numbers in the form $p^a$ work, where $p$ is a prime.

For numbers in the form $n=p^aq^b$ where $a\geq2$ and $b\geq1$ , we can take all of the factors of the form $p^k$ , and put them in the order $p, p^2, \dots , p^a$ . We then put $pq$ next to $p$ , and $p^aq$ next to $p$ and $p^a$ , respectively. Then, the rest of the factors have $q$ as a divisor, so none of them are relatively prime.

Let $n=p_1^{n_1}p_2^{n_2}\dots p_k^{n_k}$ , where $n_i\geq 1$ and $k\geq 3$ . We start by putting the integers $p_1p_2,p_2,p_3,\ldots,p_np_1$ on the circle. We then put all multiples of $p_1$ in between $p_np_1$ and $p_1p_2$ and so on with multiples of $p_k$ going between $p_{k-1}p_k$ and $p_kp_{k+1}$ . Thus, it is also possible to create such a circle for this case.

Thus, we have proved that all cases work other than the case $pq$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

Dodgers66

414 posts

Dodgers66

#15 h Oct 7, 2020, 10:08 PM • 2 Y

Y by jhu08, ImSh95

Extremely clunky solution:
We claim that it works if the sum of the exponents of the prime factorization is $\ge 3$ or it is a prime power with exponent $\ge 2$ . Another way of saying this is not $p_1 \cdot p_2$ where $p_1$ and $p_2$ are primes. (and of course also not $1$ or any prime, as the problem statement asks).

It is obvious that $p_1 \cdot p_2$ is impossible as we must place $p_1,p_2,p_1p_2$ , and since there are only 3, inevitably, $p_1$ and $p_2$ must be adjacent.

The case $p^k$ works as they all share a common factor of $p$ .

The case $p_1^{e_1}p_2^{e_2}$ works as long as at least one of the exponents is $\ge 2$ . For this we can place it around the circle with $n$ at the very top, then circling around with all the powers of $p_1$ on one side and $p_2$ on the other and then spamming the multiples of $p_1p_2$ that aren't $n$ at the bottom.

If there are three or more primes, then the circle can be constructed as follows:
$p_1,(\text{all } d \mid n, p_1 \mid d, d \ne p_1p_2,p_1p_k),p_1p_2, p_2, (\text{all } d \mid n, p_1 \nmid d, p_2 \mid d, d\ne p_2p_3), p_2p_3,\ldots, p_k, p_k^2,\ldots , p_k^{e_k},p_kp_1.$ This works for more than 3 primes since from there, $p_kp_1 \ne p_1p_2$ .

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5000 posts

IAmTheHazard

#16 h Dec 8, 2020, 7:55 PM • 4 Y

Y by v4913, jhu08, centslordm, ImSh95

We define $p_1,p_2,p_3,\ldots$ as distinct arbitrary primes.
The answer is any $n$ that cannot be expressed in the form $p_1p_2$ .
First we prove that no numbers of the form $p_1p_2$ work. The factors greater than $1$ here are $p_1,p_2,p_1p_2$ . We can easily see by placing them in a circle (there is actually only one way to do this, since reflections and rotations don't change the result) that this arrangement doesn't work, since we have $p_1$ next to $p_2$ .
Now we prove that everything else works.
First, consider a number of the form $p_1^k$ for some integer $k>1$ . Clearly, all factors greater than $1$ of this number are divisible by $p_1$ , so this works.
The remainder of the solution assumes that $n$ is divisible by at least $2$ distinct primes.
Next, consider a number of the form $p_1p_2p_3\ldots p_n$ , with $n>2$ . For convenience, we define $p_{n+1}=p_1$ .
We first place $p_1,p_2,p_3,\ldots,p_n$ a circle in that order. Then, we put $p_i p_{i+1}$ between $p_i$ and $p_{i+1}$ . Afterwards, we may place any other divisors in the circle. We may do this by placing all divisors divisible by $p_1$ in between $p_1$ and $p_1p_2$ . Then place all remaining divisors divisible by $p_2$ in between $p_2$ and $p_2p_3$ , and so on. That is, we place all remaining divisors divisible by $p_i$ in between $p_i$ and $p_i p_{i+1}$ . This clearly works, since all the numbers between $p_i$ and $p_i p_{i+1}$ share a factor of $p_i$ , and $p_i p_{i+1}$ shares a factor of $p_{i+1}$ with $p_{i+1}$ .
Now suppose a number is of the form $p_1^2p_2$ . We give the following explicit construction, which can easily be verified to work. Starting from the top and going clockwise, we place: $p_1,p_1^2,p_1p_2,p_2,p_1^2p_2$ .
Finally, we can induct to every other number. Given that $p_1^{k_1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ works, for positive integers $k_1,k_2,\ldots,k_n$ , $p_1^{k_1+1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ will work as well. All factors of $p_1^{k_1+1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ are factors of $p_1^{k_1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ , except for those divisble by $p_1^{k_1+1}$ . Thus we can put all these "new factors" in between $p_1$ and $p_1 p_2$ . Then all the numbers between $p_1$ and $p_1 p_2$ share a factor of $p_1$ . Nothing else is changed, so the arrangement works. Thus we have finished the inductive step.
Now, since $p_1$ is arbitrary, we can start from either $p_1^2p_2$ or $p_1p_2p_3\ldots p_n$ with $n>2$ , and repeatedly apply the "inductive step" to reach any other composite number. Thus, we have proven that everything else works. We are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#17 h Aug 24, 2021, 12:41 AM • 3 Y

Y by centslordm, jhu08, ImSh95

The answer is all $n$ which is not the product of two primes. Clearly, products of two primes fail, because in a circle of three elements, every two elements are adjacent. Yet the two distinct prime factors will be adjacent to each other, violating the problem condition. To show that all other numbers work, we proceed by induction on the number of distinct prime factors in $n$ .

Base Case. We will show that $n=p^k$ for $k \geq 2$ satisfy the conditions. Consider arranging the $k$ numbers in a circle in the order $p, p^2, p^3, p^4, \cdots, p^k$ . This clearly works. (In fact, any placement of the numbers around the circle works!)

We also need to show that $n=pqr$ satisfies the conditions, for primes $p, q, r$ . This is not hard; arrange the numbers in the order $1, p, pq, q, qr, r, pr, pqr$ . Clearly no two divisors are relatively prime.

Inductive Step. Assume that $n= p_1^{k_1} p_2^{k_2}\cdots p_i^{k_i}$ satisfies the condition. We will show that $n' = p_1^{k_1} p_2^{k_2}\cdots p_i^{k_i}p_{i+1}^{k_{i+1}}$ satisfies the conditions. Arrange the divisors of $n$ in a valid circle, which we know exists. Then, insert all divisors of $n'$ that contain $p_{i+1}$ (aka all divisors of $n'$ that are not divisors of $n$ ) consectutively into the circle, between $n$ and some number $j$ . We can arrange the numbers such that the number adjacent to $n$ is $n'$ , while the number adjacent to $j$ is $p_{i+1} \cdot j$ . Since all the numbers between $n$ and $j$ satisfy the conditions, and so do the numbers in the consecutive ``block" (since they all contain the factor $p_{i+1}$ ) and the numbers between the two blocks, we have a valid placement for $n'$ , as desired.

Thus the induction is complete, and the assertion holds for all $n$ not the product of two primes.

This post has been edited 1 time. Last edited by HamstPan38825, Aug 24, 2021, 12:41 AM

Z K Y

The post below has been deleted. Click to close.

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

minusonetwelth

225 posts

minusonetwelth

#34 h Aug 13, 2022, 8:21 PM • 1 Y

Y by Mango247

The answer is all prime powers and numbers with at least 4 divisors, none of which is equal to 1. (This is equivalent to saying that it works for positive integers not of the form $n=pq$ , where $p$ and $q$ are primes). For prime powers, every arrangement works. So assume $n$ is not the power of a prime.
Claim
Proof of the claim
Now assume that $n$ is has less than four divisors and is not a prime power, i.e. it is of the form $pq$ and thus has divisors $pq,p,q$ . This forces $p$ and $q$ besides each other, so this case does not work.

Z K Y

The post below has been deleted. Click to close.

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

Pleaseletmewin

1574 posts

Pleaseletmewin

#35 h Aug 26, 2022, 5:09 PM

Y by

I believe the following solution is much cleaner than a lot of the solutions on the thread, so long as it's not a fakesolve (if anyone could check for me).
Call all $n$ that satisfy the condition expressible. The key claim is the following:
Claim: Suppose $n$ is expressible and let $p$ be a prime such that $\gcd(n,p)=1$ . Then, for every integer $k\geq 1$ , $np^k$ is also expressible.
Proof. Suppose the divisors of $n$ are $d_1, \dots, d_m$ arranged in that order as well. Then, we will arrange the divisors of $np^k$ as such:
$\begin{align*} \dots , d_2, d_1, pd_1, (\text{all other divisors that are a multiple of } p), pd_2, \dots, pd_m, d_m. \end{align*}$ Since $p^2$ where $p$ is a prime is expressible, all nonsquarefree $n$ are expressible. Now, we look at squarefree $n$ . Clearly, $pq$ is not expressible but $pqr$ is, as the following arrangement works:
$\begin{align*} p, pq, pqr, q, qr, r, pr. \end{align*}$ Hence, all squarefree $n$ that have more than $3$ distinct prime divisors are expressible. Therefore, all composite $n$ are expressible except for when $n=pq$ where $p,q$ are distinct primes.

This post has been edited 2 times. Last edited by Pleaseletmewin, Aug 26, 2022, 5:11 PM

Z K Y

The post below has been deleted. Click to close.

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

NTistrulove

183 posts

NTistrulove

#36 h Aug 29, 2022, 6:35 PM • 1 Y

Y by kamatadu

The answer is $n\in \mathbb{Z}^+-\left\{\{p_ip_j\}\cup \{p_i\}\right\}$ , where $p_i$ and $p_j$ are primes

Let the arrangement with no two adjacent divisors being relatively prime be good. For $n=p_ip_j$ , the divisors are $p_i,p_j$ and $p_ip_j$ . Since $\gcd(p_i,p_j)=1$ and $p_i,p_j$ will be adjacent in every possible arrangement, so no good arrangement is possible.

Claim: A good arrangement is possible for $n=p^k$ and $n=p_1p_2\cdots p_k$ , where $p,p_1,p_2,\cdots,p_k$ are primes and $k>2$

Proof: For $n=p^k$ , the divisors of $n$ are $\{p,p^2,\cdots, p^k\}$ . Since $\gcd(p^m,p^n)>0$ for $m,n>0$ , then every arrangement is a good arrangement.

For $n=p_1p_2\cdots p_k$ , we will use induction. We have that, for $n=p_1p_2p_3$ , we get
$[asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_1$", (-3.53553390593,3.53553390593), NW); label("$p_1p_3$", (-5,0), W); label("$p_3$", (-3.53553390593,-3.53553390593), SW); label("$p_3p_2$", (3.53553390593,-3.53553390593), SE); label("$p_2p_1$", (5,0), E); label("$p_2$", (3.53553390593,3.53553390593), NE); [/asy]$
So a good arrangement is possible for $k=3$ . Assume that, it is possible to arrange for $k=k-1$ . Thus, the arrangement will look like
$[asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_ap_b\cdots$", (-3.53553390593,3.53553390593), NW); label("$\vdots$", (-5,0), W); label("$\ddots$", (-3.53553390593,-3.53553390593), SW); label("$\cdots$", (3.53553390593,-3.53553390593), SE); label("$p_ip_j\cdots$", (5,0), E); label("$\ddots$", (3.53553390593,3.53553390593), NE); [/asy]$
where $a,b,i,j\leq k-1$ . For $k=k$ , we have $n=p_1p_2\cdots p_k$ . Now, we can group the divisors having $p_k$ in them. Thus we get,
$[asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_ap_b\cdots$", (-3.53553390593,3.53553390593), NW); label("$\vdots$", (-5,0), W); label("$p_ip_j\cdots$", (-3.53553390593,-3.53553390593), SW); label("$p_ip_k$", (3.53553390593,-3.53553390593), SE); label("\vdots", (5,0), E); label("$p_jp_k\cdots$", (3.53553390593,3.53553390593), NE); [/asy]$
Therefore, $n=p_1p_2\cdots p_k$ can have a good arrangement for $k>2$ . $\blacksquare$
From above proof of $n=p_1p_2\cdots p_k$ , we can infer that if $n$ has a good arrangement, then $np$ also has a good arrangement for $p$ being a prime. Since $n=p_1p_2\cdots p_k$ is possible, then $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ is also possible for $a_i\geq 0$ . Thus all composite $n$ are possible, except $n=p_ip_j$

This post has been edited 1 time. Last edited by NTistrulove, Sep 3, 2022, 7:01 AM

Z K Y

The post below has been deleted. Click to close.

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

Msn05

39 posts

Msn05

#37 h Nov 25, 2022, 6:28 PM

Y by

My first combinatorics post :-D

. Hope I didn't fakesolve
The answer is all $n$ that are not represented as $n=p_1p_2$ for distinct primes $p_1,p_2$ .

There are three cases for $n$ :

1) $n=p^a$ . This is always possible since all divisors of $n$ greater than 1 are divisible by $p$ and thus are not coprime with each other.

2) $n=p_1p_2$ for distinct primes $p_1,p_2$ . This is impossible since there are only three divisors of $n$ greater than 1 and $p_1,p_2$ are always adjacent in a circle and are relatively prime.

3) $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ for distinct primes $p_1,p_2, \cdots p_k$ . We set the construction of this case like this: Define $b_i$ as a group of divisors of $n$ greater than 1 that are divisible by $p_i$ , not divisible by $p_j$ and the last term being divisible by $p_{i+1}$ for $1 \leq j \leq k-1, 1 \leq i \leq k, j<i$ (To avoid confusion we define $k+1 \equiv 1$ ). Note that in this configuration, the last term of $b_k$ will be divisible by $p_1$ . For example terms of $b_1$ will include all divisors that are divisible by $p_1$ except the last term of $b_k$ , terms of $b_2$ will not be divisible by $p_1$ , terms of $b_3$ will not be divisible by $p_1, p_2$ and so on. Now when these groups are in order in a circle, all the divisors adjacent to each other will not be coprime and we're done.

This post has been edited 1 time. Last edited by Msn05, Nov 25, 2022, 6:32 PM

Z K Y

The post below has been deleted. Click to close.

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

coolmath_2018

2807 posts

coolmath_2018

#38 h Feb 20, 2023, 4:28 PM

Y by

There are three cases to consider, when $n = p_1^{e_1}$ , $n = p_1p_2$ and $n = p_1^{e_1} p_2^{e_2}p_3^{e_3} \cdots p_k^{e_k}$ . For the first case $n = p_1^{e_1}$ it is obvious on how to put the factors in the circle. For the second case $n = p_1p_2$ we claim that it is impossible to put them on a circle and this obvious as to why. Now we look at the case when $n = p_1^{e_1} p_2^{e_2}p_3^{e_3} \cdots p_k^{e_k}$ . Here is the construction:

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4220 posts

RedFireTruck

#39 h Apr 12, 2023, 10:15 PM

Y by

Z K Y

The post below has been deleted. Click to close.

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

Danielzh

480 posts

Danielzh

#40 h May 9, 2023, 4:50 PM

Y by

We claim that all $n$ will work except for those in the form $n=p_{1}*p_{2}$ , where $p_{1}$ and $p_{2}$ are primes.

First we will show that $n=p_{1}*p_{2}$ does not work (trivial)

Construction:

We start with an empty circle. Let $n=p_{1}^{a_{1}}*p_{2}^{a_{2}}*...$ . Add $n$ to this circle. Then, pick a prime from the prime factorization of $n$ (WLOG $p_{1}$ ) and repeatedly add multiples of it to the circle, ensuring that the last added factor contains another factor.

For example: consider $n=2^{2}*3^{2}=36$

Once such configuration would be 36 - 2 - 4 - 18 - 12 - 6 - 3 - 9 - 36

This construction only doesn't work when a "transition" that is already taken: meaning that the transition (which is the product of 2 primes) is $n$ , and since we have already proved that, we are done. $\blacksquare{}$

Z K Y

The post below has been deleted. Click to close.

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

Danielzh

480 posts

Danielzh

#41 h May 9, 2023, 10:46 PM

Y by

Another solution cuz why not

We claim that $n$ can be all compositive positive integers except for those in the form $p_{1}*p_{2}$ .

We begin by adding $n$ to the circle. We can split the problem up into 3 cases as follows:

$\textbf{Case 1}$

$n=p_{1}^{q_{1}}$ , where $p_{1}$ is prime. It is trivial that such a configuration must occur.

$\textbf{Case 2}$

$n=p_{1}*p_{2}$ , where $p_{1}$ and $p_{2}$ are both prime. It is also trivial that there are no configurations that satisfy the problem conditions.

$\textbf{Case 3}$

$n=p_{1}^{q_{1}}*p_{2}^{q_{2}}*...*p_{k}^{q_{k}}$ , where $p_{i}$ is prime for all $1 \le i \le k$ . For simplicity, WLOG $p_{1} < p_{2} < ... < p_{k}$ . Define a "transition" as $p_{a}*p_{a+1}$ for $1 \le a \le k-1$ . Add all "transitions" in order $p_{1}, p_{2}, ..., p_{k}$ to the circle in a clockwise manner. Then, for the remaining factors, insert them immediately after the second occurrence of the least prime factor, reading from $n$ , EXCEPT for $p_{1}$ , where you can insert it after $n$ .

This completes the proof. $\blacksquare{}$

This post has been edited 1 time. Last edited by Danielzh, May 9, 2023, 10:46 PM

Z K Y

The post below has been deleted. Click to close.

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

pinkpig

3761 posts

pinkpig

#42 h Nov 22, 2023, 11:36 PM

Y by

sol

This post has been edited 4 times. Last edited by pinkpig, Nov 22, 2023, 11:41 PM

Z K Y

The post below has been deleted. Click to close.

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

CoolJupiter

925 posts

CoolJupiter

#43 h Dec 5, 2023, 8:27 PM

Y by

Claim: We claim that only composite $n$ that are not of the form $n = pq$ where $p, q$ are distinct primes work.

To quickly show $n = pq$ is not feasible, observe that $p$ and $q$ must be adjacent in the circle, which is absurd. To finish our claim, we aim to demonstrate a construction for every other possible prime factorization, which we will do in cases.

Case 1: $n = p^a$ for some prime $p$ and some integer $a \ge 2$ .

Every divisor besides $1$ of $n$ is divisible by $p$ , so any arrangement works.

Case 2: $n = p^a q^b$ work for distinct primes $p, q$ and $a, b$ are positive integers with $(a, b) \ne (1, 1)$ .

We demonstrate a construction. Observe that for numbers of the form $n = p^a q^b$ , we can construct the cycle (arrangement of the divisors in the circle)
$p \to p^2 \to p^3 \dots \to p^a \to$ $p^2q \to p^3q \to \dots \to p^aq \to$ $pq^2 \to p^2q^2 \to p^3q^2 \dots \to p^aq^2 \to$ $pq^3 \to p^2q^3 \to p^3q^3 \dots \to p^aq^3 \to$ $\dots$ $pq^b \to p^2q^b \to p^3q^b \dots \to p^aq^b \to$ $q \to q^2 \to q^3 \dots \to q^b \to pq$
Case 3: $n$ has at least $3$ prime factors.

Let $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ be the prime factorization of $n$ , where $p_i$ are distinct prime factors of $n$ , and $p_1 < p_2 \dots < p_k$ . Observe that we can classify any divisor of $d~|~n$ with a $k$ -sized binary tuple, where a $1$ in the $i$ -th position means $p_i~|~d$ , and a $0$ denotes otherwise. For example, if a divisor generated the tuple $(0, 1, 1, 0, 1)$ , it has $p_2, p_3, p_5$ as factors.

With this new definition in mind, observe that it suffices to construct a cycle of all binary tuples of size $k$ except the all- $0$ tuple, such that any adjacent tuples have a $1$ in the same position (This is sufficient as we can group terms with the same generated tuple together.) We proceed with induction for $k \ge 3$ , here is a construction for $k = 3$ :
$(1, 0, 0) \to (1, 1, 0) \to (0, 1, 0) \to (0, 1, 1) \to (0, 0, 1) \to (1, 0, 1) \to (1, 1, 1)$ Now assume that for $k = t$ , there exists some cycle $X_1 \to X_2 \dots \to X_{2^t - 1}$ that works. To finish the induction, we construct a valid cycle for $k = t + 1$ . Without loss of generality, assume that $X_{2^t - 1}$ is the all- $1$ tuple of size $t$ . Suppose $A_i$ and $B_i$ are the tuple $X_i$ with an extra $0$ and $1$ appended to the rightmost end respectively for integers $1 \le i \le 2^t - 1$ . Then
$A_1 \to A_2 \dots \to A_{2^t - 1} \to B_1 \to (0, 0, \dots, 1) \to B_2 \dots \to B_{2^t - 1}$ is a valid sequence, where the tuple between $B_1$ and $B_2$ contains $t$ zeroes. Therefore, the induction is complete, and all positive integers $n$ with at least $3$ prime factors work.

Collectively, all of our steps show that only composite positive integers $n$ that satisfy the condition cannot be expressed as the product of two distinct primes. Our proof is complete. $\blacksquare$

This post has been edited 4 times. Last edited by CoolJupiter, Dec 5, 2023, 8:34 PM

Z K Y

The post below has been deleted. Click to close.

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

gladIasked

623 posts

gladIasked

#44 h Dec 26, 2023, 3:05 AM

Y by

The answer is all integers not of the form $pq$ , where $p$ and $q$ are prime numbers. We will show that all other integers work. It's easy to see that numbers of the form $p^k$ , $k\ge 1$ work because $p$ divides each one of the divisors of $p^k$ .

Next, consider the case $n=p^{k_1}\cdot q^{k_2}$ where $k_1$ , $k_2$ are not both equal to $1$ . Also, WLOG $k_1\ge k_2$ . Place $p$ and $q$ in the circle first. We can then find two numbers that are able to "fill" the gap between $p$ and $q$ , say $pq$ and $p^2q$ . It's easy to see then that we can place the remaining divisors of $p^{k_1}\cdot q^{k_2}$ to make a good circle, as shown in the following construction:

Finally, consider the case $p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ . Like before, place $p_1$ , $p_2$ , $\ldots$ , $p_m$ in the circle first. Then, use $p_1p_2$ , $p_2p_3$ , $\ldots$ , $p_{m-1}p_m$ to "fill" the gaps between adjacent primes. It's to easy to see then that we can place the remaining divisors of $n$ to make a good circle, shown in the construction below.

It's trivial to see that all $n=pq$ fail, so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

kamatadu

466 posts

kamatadu

#45 h Dec 29, 2023, 7:07 PM • 1 Y

Y by GeoKing

All positive integers work except $\left\{1,pq\right\}$ where $p$ and $q$ are two distinct primes.

Divide into cases where the prime factorization has $\ge 3$ primes in it, $2$ or $1$ .

$p^k$ clearly works for $k\ge 1$ and $pq$ clearly doesn't work for distinct $p$ , $q$ .

For the base case for $k=3$ , we have the image below.

Now for an increase in the value of $k$ to $k+1$ , note that the divisors that get introduced are $p_{k+1} \times \left\{\text{set of divisors of } p_1\cdot p_2 \cdots p_k\right\}$ . For this we can select a divisor from the configuration for $k$ from induction and its neighboring divisor and then insert the new divisors as shown below.

For increasing the power of a prime (WLOG $p_1$ ) in the factorization from $e$ to $e+1$ , we can see that the new divisors that get introduced are those who have $\nu_{p_1}(\text{divisor}) = e+1$ . Now note in the configuration of the inductive hypothesis, that the divisor adjacent to $p_1$ must also have $p_1$ in it. Thus we can insert all the new divisors in between the two selected divisors as shown below.

And we are done. :yoda:

Z K Y

The post below has been deleted. Click to close.

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

surpidism.

10 posts

surpidism.

#46 h May 27, 2024, 7:34 PM

Y by

The answer is all composite numbers not of the form $pq$ , where p, q are primes.
It is easy to see by hand that $n = pq$ doesn't work.
Also, $n = p^a$ , where $a \geq 2$ works. Arrange the divisors as { $p$ , $p^2$ , ... , $p^a$ , $p$ }, which works.

Now we show that $n = p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_m^{a_m}$ where, $m \geq 2$ , $a_i \geq 1$ , works . We do so using induction.

Base case: $m = 2$
Consider the arrangement, { $p_1$ , $p_1^2$ , ... , $p_1^{a_1}$ , $p_1 p_2$ , $p_2$ , $p_2^2$ , ..., $p_2^{a_2}$ , $p_1 p_2^2$ , ... , $p_1^{a_1} p_2^{a_2}$ , $p$ }, which clearly works

Inductive hypothesis: Assume for $m = k$ , the required arrangment is possible.

Inductive step: For $m = k+1$
By inductive hypothesis, we have an arrangement for $n = p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_k^{a_k}$ . We make the construction for $m = k+1$ by placing the divisors containing $p_{k+1}$ in the arrangement of $m = k$ . We place $p_{k+1} \cdot p_1$ next to $p_1$ then all the divisors that contain $p_{k+1}$ and finally $p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_k^{a_k} \cdot p_{k+1}^{a_{k+1}}$ .

This works and we are done. $\square$

This post has been edited 2 times. Last edited by surpidism., May 28, 2024, 4:20 AM

Z K Y

The post below has been deleted. Click to close.

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

blueprimes

313 posts

blueprimes

#47 h Aug 2, 2024, 3:28 PM

Y by

The answer is all positive integers $n$ that cannot be expressed as $pq$ where $p$ , $q$ are distinct primes. For sufficiency note that $p$ and $q$ must be adjacent in the cycle which are relatively prime. Now we will provide a construction for all other possibilities.

$\textbf{Case 1:}$ $n$ is a prime power.
All divisors in the cycle are divisible by some prime, so this is valid.

$\textbf{Case 2:}$ $n = p^a q^b$ where $p$ , $q$ are primes and $a, b \ge 1$ , $\max(a, b) \ge 2$ .
Consider the construction
$pq \to p \to p^2 \to \dots \to p^a \to (\text{sequence of divisors divisible by } pq \text{ except } pq) \to q \to q^2 \to \dots \to q^b$ which is a valid cycle.

$\textbf{Case 3:}$ $n$ has at least $3$ prime divisors.
First we show for squarefree $n = p_1 p_2 \dots p_k$ where $p_i$ are primes and $k \ge 3$ . We proceed with induction, the base case $k = 3$ achieved by the following cycle:
$p_1 \to p_1p_2 \to p_2 \to p_2p_3 \to p_3 \to p_1p_3 \to p_1p_2p_3$ Now assume a valid cycle exists for $k = t$ . To prove for $k = t + 1$ , we will insert the new divisors after $p_1p_2 \dots p_t$ in the $k = t$ cycle. We have the valid cycle
$\underbrace{a \to (\text{some valid sequence}) \to p_1 p_2 \dots p_t \to p_1 p_2 \dots p_{t + 1}}_{\text{cycle for } k = t} \to (\text{any sequence of divisors divisible by } p_{t + 1})$ where the last sequence ends in $ap_{t + 1}$ . Now clearly if a cycle exists for $n = p_1 p_2 \dots p_k$ we can extend it to all $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ for $e_i \ge 1$ as we can simply bunch divisors with the same set of prime factors.

We have exhausted all other cases, and our proof is complete.

This post has been edited 1 time. Last edited by blueprimes, Aug 2, 2024, 3:28 PM

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

310 posts

Ilikeminecraft

#48 h Today at 1:46 AM

Y by

The answer is all $n\neq pq,$ where $p, q$ are primes.
If it is of this form, it obviously doesn't work. We now split it into 3 cases.
If $n$ has 1 prime dividing it: Simply take $1, p, \dots, p^k$ which finishes
If $n$ has 2 primes: take $pq, p, p^2, \dots, p^a, \text{all multiples of }pq, q, q^2, \dots, q^b$ which finishes
If $n$ has 3+ primes: First, note that $pqr$ can be done by $p, pq, q, qr, r, pr, pqr.$ Then, to multiply by any prime(not necessarily relatively prime), for each term, append it by the prime multiplied by the term. e.g., $pqr\cdot s$ would become $p, ps\mid, pq, pqs\mid, \dots$

Z K Y