Good Partitions

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

Good Partitions

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: 2015 ISL C3

The post below has been deleted. Click to close.

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

1276 posts

va2010

#1 h Jul 7, 2016, 9:13 PM • 8 Y

Y by quangminhltv99, Davi-8191, tenplusten, qubatae, NTSQWER, Adventure10, NicoN9, taki09

For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$ . Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

This post has been edited 5 times. Last edited by va2010, Jul 8, 2016, 7:04 PM

Z K Y

The post below has been deleted. Click to close.

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

3564 posts

62861

#2 h Jul 7, 2016, 11:29 PM • 3 Y

Y by Adventure10, Mango247, taki09

This is C3.

Z K Y

The post below has been deleted. Click to close.

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

21 posts

#4 h Jul 8, 2016, 8:15 AM • 3 Y

Y by Adventure10, Mango247, taki09

Answer.
Click to reveal hidden text

Solution.
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.

2487 posts

#5 h Jul 8, 2016, 9:25 AM • 4 Y

Y by swimmerstar, Adventure10, Mango247, taki09

Call a fence to be a delimiter partitioning the set. By an easy argument on bounding if we arrange the set in increasing order we get that at most two fences can be together. Then a construction can easily be obtained by looking at equality cases.

Z K Y

The post below has been deleted. Click to close.

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

233 posts

#6 h Jul 8, 2016, 12:55 PM • 3 Y

Y by Adventure10, Mango247, taki09

Hello.

This was also problem 4 in 2016 Greece Team Selection Test.

Z K Y

The post below has been deleted. Click to close.

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

2679 posts

#7 h Jul 14, 2016, 2:06 AM • 1 Y

Y by Adventure10

Let the elements of $A$ be $a_1, a_2,\ldots, a_k$ . In a good partition call the GCD/LCM the midpoint, and let $g_1$ be the midpoint of the good partition with smallest midpoint. Then $A_1$ has some integers with an LCM of $g_1$ and every element of $A_2$ is divisible by $g_1$ , implying every element of $A_2$ is greater than the maximal element of $A_1$ (because $g_1$ only appears once if it is an element). Then, let $a_i=g_1\cdot b_i$ for some integer $b_i$ for the $a_i$ in $A_2$ , so if $|A_1|=s$ we have $\gcd(b_{s+1},\ldots, b_k)=1$ .

Let $g_2$ be the second-smallest midpoint, and note that $g_2\in A_2$ because it is greater than $g_1$ . (All references to $A_1$ and $A_2$ will be to the first partition unless otherwise mentioned.) Thus, it is a multiple of $g_1$ . If $g_1=g_2$ then we have $A_1, A_2$ remaining the same except for $g_1$ switching (this requires $g_1$ to be an element); however, this means we cannot have $g_3=g_2$ where $g_3$ is the third-smallest midpoint. If $g_2>g_1$ , then we cannot have $g_2=a_{s+1}$ because if so, the LCM of the new $A_1$ will be $a_{s+1}$ but if the GCD of the new $A_2$ is $a_{s+1}$ , we have $\gcd(b_{s+1},\ldots, b_k)=\frac{a_{s+1}}{g_1}$ contradicting $\gcd(b_{s+1},\ldots, b_k)=1$ . Similarly, if $g_2=a_{s+2}$ , then $a_{s+2}$ divides all of $a_{s+3},\ldots, a_k$ and is also a multiple of $a_{s+1}$ , a contradiction because then $\gcd(b_{s+1},\ldots, b_k)=\frac{a_{s+1}}{g_1}$ .If $g_2\not\in A_2$ , then it must be greater than $a_{s+2}$ (if it wasn’t, then it would be a multiple of $a_{s+1}$ and would divide into all the greater $a_i$ so we would get a similar contradiction.

As every element of $A_2$ is greater than the maximal element of $A_1$ , every partition can be represented by a separation (which we will call a break between $a_j, a_{j+1}$ for some $j$ . If some $g_i$ is not one of the $a_i$ then it will be between $a_j, a_{j+1}$ . We have thus proven that there must be at least two elements between each break unless the $g_i$ is part of the set, so the maximal number of good partitions from a set of size $t$ comes from placing a break after the first element (we cannot break before that) and placing breaks around every 3rd element after that, as if we deviate from this we cannot be any more compact and at best we will have the same number of good partitions. We can then calculate $t=3024$ as the smallest for 2015 good partitions, and an example is $\{1,2,3,6,6\cdot 2, 6\cdot 3, 6^2, 6^2\cdot 2, 6^2\cdot 3, 6^3,\ldots, 6^{1007}, 6^{1007}\cdot 2, 6^{1007}\cdot 3 \}.$

Z K Y

The post below has been deleted. Click to close.

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

3070 posts

#8 h Jul 22, 2016, 9:35 AM • 2 Y

Y by Adventure10, Mango247

This is also India TST 2016, Day 2, Problem 3.

Z K Y

The post below has been deleted. Click to close.

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

339 posts

#9 h Jul 23, 2016, 5:43 AM • 4 Y

Y by Davi-8191, Lam.DL.01, Adventure10, SimogmH1

Hopefully this works...

Click to reveal hidden text

This post has been edited 2 times. Last edited by AnonymousBunny, Jul 23, 2016, 6:00 AM

Z K Y

The post below has been deleted. Click to close.

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

54 posts

#10 h Feb 13, 2018, 1:55 AM • 3 Y

Y by Adventure10, Mango247, taki09

The minimum such $n$ is $3024$ .

First, note that $A_1$ can only have elements smaller than elements of $A_2$ as otherwise lcm( $A_1$ ) > biggest element in $A_1$ > smallest element in $A_2$ > gcd ( $A_2$ ). So sort the numbers in $A$ in increasing order. For a number $a$ , let $S_a$ be the set of numbers less than or equal to $a$ . Call a number nice if partition of $A_1 = S_a$ and $A_2 = A-A_1$ is good.

Suppose there are two consecutive numbers $x$ and $y$ that are nice. Then gcd( $S_y$ ) = gcd $(S_x) \cdot k$ . If $k \neq 1$ , then gcd $(S_x)\cdot k$ dividing the numbers bigger than $y$ is a contradiction to $x$ being nice. Since the elements in a set are distinct, it means that we can't have three consecutive numbers that are nice. It also follows easily that if the last block of nice numbers have size $2$ , there must be at least two numbers after that are not nice. We can also see from the above that we can't start with two nice numbers. And on the other hand, if the last block of nice numbers have size $1$ , there must be at least one number after that's not nice.

Now suppose $n <= 3023$ . If the number of blocks of nice numbers are at least $1010$ , then we need $n \ge 2015+1009$ , which is impossible; since we need to split $2015$ into blocks of size at most $2$ , the number of blocks of nice numbers must be $1008$ with only one block of just one nice number or $1009$ with two blocks of a single nice number. We first need $\ge 1007$ numbers that are not nice between blocks, thus having $n = 2015+1007$ for previous case and $n$ at least $2015+1008$ . Then by previous observations, no matter where that block/two blocks of a single number is, we always need another space in the beginning or end.

Construction for n = 3024

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#11 h Oct 7, 2018, 5:59 AM • 1 Y

Y by Adventure10

The answer is $\boxed{n=3024}$ . Let $A=\{a_1<a_2<\cdots<a_n\}$ . Suppose $(A_1,A_2)$ is a good partition of $A$ . We see that $\max A_1\mathrm{lcm}A_1=\gcd A_2\le \min A_2$ , so all elements of $A_1$ are less than elements of $A_2$ . In particular, this implies $A_1=\{a_1,\ldots,a_k\}$ and $A_2=\{a_{k+1},\ldots,a_n\}$ for some $1\le k\le n-1$ . Let $B_k=\{a_1,\ldots,a_k\}$ and $C_k=\{a_{k+1},\ldots,a_n\}$ . Again, all good partitions must be of the form $(B_k,C_k)$ .

Lemma: If $(B_k,C_k)$ and $(B_{k+1},C_{k+1})$ are both good, then $\mathrm{lcm}B_k = \mathrm{lcm}B_{k+1} = a_{k+1}$ .

Proof of Lemma: Let $d_k=\mathrm{lcm} B_k = \gcd C_k$ and $d_{k+1}=\mathrm{lcm}B_{k+1}=\gcd C_{k+1}$ . We see that $d_{k+1}=\mathrm{lcm} B_{k+1} = \mathrm{lcm}(d_k,a_{k+1})$ , and $d_k=\gcd C_k=\gcd(d_{k+1},a_{k+1})$ . The result is not hard to see from here, but we outline the proof for sake of completeness. Note that
$d_k=\gcd(\mathrm{lcm}(d_k,a_{k+1}),a_{k+1}).$ Let $x=\nu_p(d_k)$ and $y=\nu_p(a_{k+1})$ where $p$ is any prime. We wish to show $x=y$ . We have $x=\min\{\max\{x,y\},y\}$ . If $x\le y$ , then $x=\min\{y,y\}=y$ , and if $x\ge y$ , then $x=\min\{x,y\}=y$ , so in all cases $x=y$ as desired. Thus, $d_k=a_{k+1}$ . We can do a similar argument to show that $d_{k+1}=a_{k+1}$ , so we have $d_k=d_{k+1}=a_{k+1}$ , as desired. $\blacksquare$

From the lemma, we see that we can't have $(B_k,C_{k}),(B_{k+1},C_{k+1}),(B_{k+2},C_{k+2})$ all be good. Also the lemma implies that we can't have both $(B_1,C_1),(B_2,C_2)$ be good, since the lemma would imply $a_1=a_2$ , which isn't possible. Thus, we must have $n\ge 3024$ , else by pigeonhole, we would have three such consecutive good partitions, or both $(B_1,C_1),(B_2,C_2)$ be good.

We now provide a construction for $n=3024$ . Let $p_1,\ldots,p_{1008},q_1,\ldots,q_{1008}$ all be distinct primes. The construction goes as follows. Let $a_{3m}=\prod_{i=1}^m p_iq_i$ , $a_{3m+1}=a_{3m}p_{m+1}$ , and $a_{3m+2}=a_{3m}q_{m+1}$ where we define $a_0=1$ . The construction starts off like
$p_1,q_1,p_1q_1,p_1q_1p_2,p_1q_1p_2,p_1q_1p_2q_2,\ldots.$ Here, $(B_k,C_k)$ is good if and only if $k\equiv 0,2\pmod{3}$ .

This post has been edited 1 time. Last edited by yayups, Oct 7, 2018, 6:09 AM

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#12 h Apr 14, 2019, 6:55 PM • 1 Y

Y by Adventure10

If $S,T$ are two sets of integers, I say that $S|T$ if $s|t\,\,\forall s\in S,t\in T$ . It is clear that if a partition is good, then $A_1|A_2$ . Suppose we have a good partition: $(A,B)$ . Given another good partition $(C,D)$ , note that if we had $a\in A$ and $b\in B$ , we cannot have $a\in D$ and $b\in C$ , since that would imply that $a|b$ and $b|a\implies a=b$ , which contradicts the fact that $A$ is a set. So, if $A\cap D=A'\neq\emptyset$ , then we know that $B\subset D$ , so $C=A\setminus A'$ , $D=B\cup A'$ . We already know that $A\setminus A' | B$ , so this new partition tells us that $A\setminus A'|A'$ . So, $(A\setminus A',A')$ is a good partition of the set $A$ , and we can write $A\setminus A'|A'|B$ . The statement to the left, in fact, basically encapsulates everything we know about set $A$ up to this point.

To generalize this result, suppose we know that $A$ is the disjoint union of the sets $S_1,S_2,\ldots,S_n$ , and $S_1|S_2|\ldots |S_n$ . Then, if we find a new good partition of $A$ , such that the set $S_k$ is split between the two parts of the partition (if no $S_k$ exists, then this obviously isn't a new good partition), we know that $S_1,S_2,\ldots,S_{k-1}\subset A_1$ , and $S_{k+1},\ldots,S_n\subset A_2$ , and this partition tells us that $A_1\cap S_k|A_2\cap S_k$ . So, for every new partition we find, our "chain" of divisibilities increases by 1.

Therefore, if we have a set $A$ with at least $2015$ good partitions, then we can write it as the disjoint union of sets $S_1,\ldots S_{2016}$ , such that $S_1|S_2|\ldots|S_{2016}$ , and our good partitions will just be $\left(\bigcup\limits_{i=1}^jS_i,\bigcup\limits_{i=j+1}^{2016}S_i\right)$ as $j$ ranges from $1$ to $2015$ . Consider what happens when $|S_k|=1$ , and suppose its sole element is $a$ . Then, for our $k$ th good partition, we know that the $\text{lcm}$ of the first set is $a$ . Likewise, if $|S_{k+1}|=1$ , and its sole element is $b$ , then the RHS has $\text{gcd}$ of $b$ . However, this can't be a good partition, as $a\neq b$ since $a,b\in A$ . Therefore, if $|S_k|=1$ , then $|S_{k+1}|>1$ . Therefore, to minimize the magnitude of set $A$ , $|S_i|$ should alternate between 1 and 2, which gives $|A|=3024$ to be minimum.

As a construction, consider $S_{2i+1}=\{6^i\}$ , and $S_{2i+2}=\{2*6^i,3*6^i\}$ . It is clear that the described 2015 partitions work, and there exist no others, as there is no divisibility between the 2 elements of $S_{2i+2}$ .

This post has been edited 1 time. Last edited by william122, Apr 14, 2019, 6:57 PM

Z K Y

The post below has been deleted. Click to close.

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

1492 posts

#13 h May 27, 2020, 9:59 PM

Y by

The answer is $n = 3024.$ Let $A = \{a_1, a_2, \dots , a_n \},$ where $a_i < a_{i+1}.$ Notice that if a partition $P_k = A_k \cup B_k = A$ is good, then $\max A_k \le \text{lcm} A_k = \text{gcd} B_k \le \min B_k$ That is, the partition must look like $P_k = \{a_1, a_2, \dots a_k \} \cup \{a_{k+1}, \dots a_n \} = A.$

Claim: Among $3$ partitions $P_k$ , $P_{k+1}$ , and $P_{k+2}$ , at most $2$ can be good.
Proof:

Suppose that $P_k$ and $P_{k+1}$ are both good. Then, $\text{lcm} A_{k+1} = \text{lcm}(A_k, a_{k+1}) = \gcd(B_{k+1}).$ Notice that $A_k \mid \text{lcm}(A_k, a_{k+1})$ so $a_i \mid \text{gcd}(B_{k+1})$ for all elements $a_i \in A_k.$ Similarly, $a_{k+1} \mid \gcd(B_{k+1}).$ It thus follows that $a_i \mid a_j$ if $i \le k+1$ and $j > k + 1.$ However, it follows from $P_k$ being good that $a_i \mid a_{k+1}$ for all $i \le k,$ so $\text{lcm}(A_{k+1}) = a_{k+1}.$ Similarly, $\text{lcm} A_k = a_{k+1}.$ Therefore, if $P_{k+2}$ were good, then $\text{lcm} A_{k+2} = \text{lcm} (a_{k+1}, a_{k+2}) = a_{k+2} = \text{gcd} B_{k+2},$ but this would imply that $\text{gcd} (B_{k+1}) = a_{k+2}$ , which contradicts $\text{gcd} (B_{k+1}) = a_{k+1}.$

Notice that both of $P_1$ and $P_2$ cannot be good partitions, since this would force $a_1 = a_2,$ and neither can $P_{n}$ , so There must be at least $\frac{3}{2} \cdot 2014 + 3 = 3024$ elements in $A.$ We will now provide a construction. WLOG let $P_1$ be good, so that $a_1 \mid a_{k}$ for $k > 1.$ From here on out, $P_{3k}$ and $P_{3k+1}$ are both good. Let $a_1 = 1$ , $a_2 = 2$ , $a_3 = 3,$ $a_4 = 6$ , $a_5 = 8$ , $a_6 = 12$ , $a_7 = 24$ , etc. Indeed, a possible sequence is $a_{3k-1} = 2^{k} 3^{k-1},$ $a_{3k} = 3^k 2^{k-1},$ and $a_{3k+1} = 3^k 2^k,$ which can be easily seen to work. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

156 posts

#14 h Jul 1, 2020, 9:24 PM • 1 Y

Y by centslordm

We claim that the answer is $3024.$ To show that this is achievable, consider the set $A$ with elements $a_i$ such that $a_{3k}=p_1p_2...p_{3k}, a_{3k+1}=p_1p_2...p_{3k}p_{3k+1},$ and $a_{3k+2}=p_1p_2...p_{3k}p_{3k+2}$ for $1\le i\le 3024 ,$ where the $p_i$ are distinct primes. It is easy to see that this works.

Now, we prove the lower bound. Consider a set $A$ that has $2015$ good partitions. By the given condition, all elements of $A_1$ must divide all elements of $A_2.$ Consider a good partition such that $a$ is an element of $A_1$ and $b$ is an element of $A_2.$ Then since $a|b$ and $a\neq b,$ we cannot have $b|a,$ so there does not exist a good partition of $A$ such that $b\in A_1$ and $a\in A_2.$ Let $B_1,B_2,...B_{2015}$ be the sets $A_2$ over all good partitions of $A$ such that $|B_1|\le |B_2|\le...\le |B_{2015}|,$ and let $C_1,C_2,...,C_{2015}$ be all the sets $A_1$ over all good partitions of $A.$ By what we have shown above, $B_k$ must be a subset of $B_i$ for all $i\ge k.$

Claim. $|B_2|\ge 3$
Proof. Assume for the sake of contradiction that this is not true. Then $|B_1|$ and $|B_2\setminus B_1|$ must both be $1.$ Let $|B_2\setminus B_1|=\{b\}.$ Then $b$ must divide the element of $B_1.$ This means that the gcd of all elements of $B_2$ must be $b.$ Furthermore, all elements of $C_2$ divide $b,$ so $b$ is at least the lcm of the elements of $C_2.$ But this means that $b$ is exactly the lcm of the elements of $C_2,$ which means that it is also the lcm of the elements of $C_1,$ so the element of $B_1$ must equal $b,$ contradiction. $\blacksquare$

Claim. $|C_{2015}\cup (B_{2015}\setminus B_{2014})|\ge 3.$
Proof. Again, assume for the sake of contradiction that this is not true. Then $|C_{2015}|$ and $|B_{2015}\setminus B_{2014}|$ are both $1.$ Let $C_{2015}=\{c\}$ and $B_{2015}\setminus B_{2014}=\{b\}.$ Then we must have that $b$ divides all elements of $B_{2014},$ so $b$ is the lcm of all elements of $B_{2015}.$ But then $c=b,$ a contradiction. $\blacksquare$

Claim. If $|B_{i}\setminus B_{i-1}|=1,$ then $|B_{i+1}\setminus B_i|\ge 2$ for $1\le i\le 2014.$
Proof. Assume for the sake of contradiction that $|B_{i+1}\setminus B_i|=1,$ and let $B_i\setminus B_{i-1}=b_1$ and $B_{i+1}\setminus B_i=b_2.$ Then $b_1$ must divide all elements of $B_{i-1}.$ It follows that $b_1$ must be the gcd of all elements of $B_{i}.$ Then the gcd of all elements of $B_{i}$ must also be $b_1.$ However, $b_2$ divides all the elements of $B_i,$ and all elements of $C_{i+1}$ divide $b_2.$ This means that the lcm of all the elements of $C_i$ must be at most $b_2,$ so $b_1\le b_2.$ However this is a contradiction since $b_2|b_1$ and $b_2\neq b_1.$ Thus, the claim is proven. $\blacksquare$

From the claim above, we get that $|B_i\setminus B_{i-2}|\ge 3$ for $4\le i\le 2014.$ Finally, we must have that the total number of elements is $3\cdot 1008=3024,$ as desired.

This post has been edited 1 time. Last edited by Blossomstream, Jul 2, 2020, 12:18 AM

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#15 h Oct 31, 2020, 10:43 AM • 2 Y

Y by centslordm, Funcshun840

Solved with nukelauncher.

The answer is 3024, achieved by $\begin{align*} &&\{1{\color{red}\;\mid\;}p_1\mid q_1{\color{red}\;\mid\;}p_1q_1{\color{red}\;\mid\;}p_1q_1p_2\mid p_1q_1p_2{\color{red}\;\mid\;}p_1q_1p_2q_2{\color{red}\;\mid\;}p_1q_1p_2q_2p_3\mid p_1q_1p_2q_2q_3{\color{red}\;\mid\;}\ldots\\ &&{\color{red}\;\mid\;}p_1q_1\cdots p_{1007}q_{1007}p_{1008}\mid p_1q_1\cdots p_{1007}q_{1007}q_{1008}\}. \end{align*}$ Cloudy partitions above have been colored red.

Let $A=\{s_1<\cdots<s_n\}$ . We say $k$ is decisive if a cloudy partition is $\{s_1,\ldots,s_k\}\sqcup\{s_{k+1},\ldots,s_n\}$ . (Obviously all cloudy partitions are of this form.) The key is this estimate:

Claim: $k-1$ , $k$ , $k+1$ may not all be decisive.

Proof. Assume for contradiction all three are decisive. From $k-1$ and $k+1$ decisive, we have $\operatorname{lcm}(s_1,\ldots,s_{k-1})\mid s_k\quad\text{and}\quad s_{k+1}\mid\gcd(s_{k+2},\ldots,s_n).$ However, from $k$ decisive, $s_k=\operatorname{lcm}(s_1,\ldots,s_k)=\gcd(s_{k+1},\ldots,s_n)=s_{k+1},$ contradiction. $\blacksquare$

Claim: 1 and 2 may not both be decisive. (Analogously, $n-2$ and $n-1$ may not both be decisive.)

Proof. Assume for contradiction 1 and 2 are decisive. Then from 1 decisive, $s_1\mid s_2$ , so from 2 decisive, $s_2=\operatorname{lcm}(s_1,s_2)=\gcd(s_3,\ldots,s_n)$ , and then from 1 decisive, $s_1=\gcd(s_2,\ldots,s_n)=s_2$ , contradiction. $\blacksquare$

It is easy to check that for $n\le3023$ , there are less than 2015 cloudy partitions, so the least possible $n$ is 3024.

Z K Y

The post below has been deleted. Click to close.

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

30653 posts

#18 h Jul 23, 2021, 12:37 AM • 1 Y

Y by megarnie

a variation, with 2016 instead of 2015 good partitions, was proposed as 2016 Brazil IMO TST 3.2

This post has been edited 1 time. Last edited by parmenides51, Jul 23, 2021, 12:38 AM

Z K Y

The post below has been deleted. Click to close.

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

351 posts

#19 h Oct 9, 2021, 6:40 PM • 1 Y

Y by Bradygho

Sketch:

We claim the answer is $3024$ , which can be achieved by $\{1,2,3,6,6 \cdot 2,6 \cdot 3,6^2,6^2 \cdot 2,6^2 \cdot 3,\ldots,6^{1007},6^{1007} \cdot 2,6^{1007} \cdot 3\}.$ First, notice that any partition must be comprised of two sets such that the smallest number in one set is bigger than the biggest number in the other set. For a set $S$ , let $k$ be a cloud if the partition of $S$ into a set with the smallest $k$ elements and a set with the rest of the elements is cloudy. Let $a_1,a_2,\ldots,a_{|S|}$ be the elements of $S$ in increasing order.

Claim: $1$ and $2$ cannot both be clouds, and $|S|-1$ and $|S|-2$ cannot both be clouds.
Proof: If $1$ and $2$ are clouds, then $\gcd\left(a_2,a_3,\ldots,a_{|S|}\right)=a_1$ and $\gcd\left(a_3,a_4,\ldots,a_{|S|}\right)=\operatorname{lcm}(a_1,a_2)$ . However, we know from the first equation that $a_1 \mid a_2$ , so $\operatorname{lcm}(a_1,a_2)=a_2$ . However, that means $a_1=\gcd\left(a_2,a_3,a_4,\ldots,a_{|S|}\right)=\gcd\left(a_2,\gcd\left(a_3,a_4,\ldots,a_{|S|}\right)\right)=a_2,$ a contradiction. We can use a similar argument to prove that $|S|-1$ and $|S|-2$ cannot both be clouds.

Claim: $k$ , $k+1$ , and $k+2$ cannot both be clouds.
Proof: Using a similar idea, analyzing $\gcd$ .

Then, it's pretty easy to see that we must have at least $3024$ elements.

This post has been edited 2 times. Last edited by tigerzhang, Oct 9, 2021, 6:41 PM

Z K Y

The post below has been deleted. Click to close.

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

1671 posts

pad

#20 h Nov 21, 2021, 12:07 AM • 1 Y

Y by Chokechoke

Let $A=\{a_1<a_2<\cdots <a_n\}$ . Suppose $a\in A_1$ and $b\in A_2$ . Then $b\mid \text{lcm}(A_2)=\gcd(A_1) \mid a$ , so $b\mid a$ . In particular, $b\le a$ . Every element of $A_2$ is less than every element of $A_1$ , so we must have $A_2=\{a_1,a_2,\ldots,a_k\}$ for some $1\le k\le n$ . In $a_1,a_2,\ldots,a_n$ , put a $*$ after $a_k$ if this partition results in $\gcd(A_1)=\text{lcm}(A_2)$ .

Claim: There can never be $3$ consecutive $*$ .

Proof: Suppose $a_1\cdots a_{k-2} \ * \ a_{k-1} \ * \ a_{k} \ * \ a_{k+1} \cdots a_n$ .

$a_{k} \mid a_{k+1},\ldots,a_n$ , so $\text{gcd}(a_{k},\ldots,a_n)=a_{k}$ .
$a_1,\ldots,a_{k-2}\mid a_{k-1}$ , so $\text{lcm}(a_1,\ldots,a_{k-1})=a_{k-1}$ .

But $\text{lcm}(a_1,\ldots,a_{k-1}) = \gcd(a_{k},\ldots,a_n)$ , so $a_{k-1}=a_{k}$ , contradiction. $\blacksquare$

The Claim proves that among any $3$ consecutive spaces between numbers of $A$ , at most $2$ can contain a $*$ . Similar logic easily proves that the first two spaces cannot both contain $*$ 's. Hence the minimum number of spaces needed for $2015$ $*$ 's is $\lceil \tfrac32\cdot 2015\rceil=3023$ , so the minimum $n$ is $3023+1=3024$ .

The following construction provides $n=3024$ :
$2\cdot 3 \ * \ 2^2\cdot 3 , 2\cdot 3^2 \ * \ 2^2\cdot 3^2 \ * \ 2^3\cdot 3^2 , 2^2\cdot 3^3 \ * \ 2^3\cdot 3^3 \ * \ \ldots$ In general, we have the repeating 3-pattern of $2^k\cdot 3^k \mid 2^{k+1}\cdot 3^k, 2^k\cdot 3^{k+1} \mid$ . This works since $\gcd(2^{k+1}\cdot 3^k, 2^k\cdot 3^{k+1})=2^k\cdot 3^k$ and $\text{lcm}(2^{k+1}\cdot 3^k, 2^k\cdot 3^{k+1})=2^{k+1}\cdot 3^{k+1}$ .

Remarks

This post has been edited 3 times. Last edited by pad, Nov 22, 2021, 8:52 PM

Z K Y

The post below has been deleted. Click to close.

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

658 posts

#21 h Feb 7, 2022, 10:13 AM

Y by

In general, if we replaces $2015$ by $2l+1$ , answer is $3l + 2$ . Write
$A = \{a_1 < a_2 < \cdots < a_n \}$ Note all $A_1$ must be of the form $A_1 = \{a_1,\ldots,a_k\}$ , as every element of $A_1$ is less than every element of $A_2$ . Call a $k$ good if $A_1 = \{a_1,\ldots,a_k\}$ is cloudy and bad otherwise. For any $k$ , let $f(k) = \text{lcm}(a_1,\ldots,a_k), g(k) = \gcd(a_{k+1},\ldots,a_n)$ . Call $k$ nice if $a_k = f(k)$ .

Claim: If $k$ is good, then $k+1$ is nice

Proof: From $k$ good we get $a_1,\ldots,a_k \mid a_{k+1}$ , thus $f(k+1) = a_{k+1}$ . $\square$

Claim: If $k$ is nice and good, then $k+1$ is bad.

Proof: Assume contrary. Observe $f(k+1) = a_{k+1}$ as $a_1,\ldots,a_k \mid a_{k+1}$ (since $k$ good). Thus $g(k+1) = a_{k+1}$ . But this forces $g(k) = a_{k+1}$ . On the other hand $f(k) = a_k$ (since $k$ nice). But as $f(k) = g(k)$ , so $a_{k+1} = a_k$ , contradiction. $\square$

Claim: If $k$ is nice and good, then $k \le n-2$ .

Proof: FTSOC $k = n-1$ . Then $f(n-1) = a_{n-1}$ . But $g(n-1) = a_n$ , implying $a_n = a_{n-1}$ , contradiction. $\square$

Now our first two Claim give no three consecutive numbers are good. We have some other results too. It is not hard to see $3l+2$ is necessary. So see its sufficient, for primes $p < q$ consider
$\textcolor{blue}{1},p,\textcolor{blue}{q},\textcolor{blue}{pq},p^2q,\textcolor{blue}{pq^2},\textcolor{blue}{p^2q^2} , p^3q^2,\textcolor{blue}{p^2q^3},\textcolor{blue}{p^3q^3},\ldots,\textcolor{blue}{p^lq^l},p^{l+1}q^l, p^l q^{l+1}$ where all blue numbers are good. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

5611 posts

#22 h Jan 18, 2023, 2:30 AM

Y by

Solved with GoodMorning.

The answer is $3024$ , achievable by $(6^i, 2\cdot 6^i, 3\cdot 6^i)$ for $0\le i\le 1007$ .

Now we show that $n\ge 3024$ . Let $A = \{a_1, a_2, \ldots, a_n\}$ , where $a_1<a_2<\cdots < a_n$ .

Notice that a good partition must be of the form $A_1 = \{a_1, a_2, \ldots, a_x\}, A_2 = \{a_{x+1}, a_{x+2}, \ldots, a_n\}$ for some $x$ . Let $P_x$ denote this partition for each $1\le x\le n-1$ .

Claim: There are no three consecutive good partitions.
Proof: Suppose that for some $x$ , we have $P_{x-1}, P_x, P_{x+1}$ are all good partitions. Then we notice that $a_1, a_2, \ldots, a_{x-1}$ all divide $a_x, a_{x+1},\ldots, a_{n}$ .

Also, $a_x\mid a_{x+1}, a_{x+2}, \ldots, a_n$ and $a_{x+1}\mid a_{x+2}, a_{x+3}, \ldots, a_n$ .

This implies that $\mathrm{lcm}(a_1, a_2, \ldots, a_x) = a_x$ and $\gcd(a_{x+1}, a_{x+2}, \ldots, a_n) = a_{x+1}$ ,so $a_x = a_{x+1}$ , contradiction.
$\square$

Its easy to see that $P_1$ and $P_2$ cannot both be good (and similarly $P_{n-1}$ and $P_{n-2}$ can also not both be good), so for $n\le 3023$ , we must have at most $\frac{3018}{3}\cdot 2 + 2 = 2014$ partitions, which implies $n\ge 3024$ .

This post has been edited 1 time. Last edited by megarnie, Jan 18, 2023, 2:30 AM

Z K Y

The post below has been deleted. Click to close.

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

1051 posts

#23 h Feb 20, 2023, 12:08 AM

Y by

The answer is $3024$ . Select your favorite primes $p$ and $q$ . The set $A = \{p^kq^k,p^{k+1}q^k, p^{k}q^{k+1} \}$ for each positive integer $1 \leq k \leq 1008$ works.

First, suppose we have a partition with $|A_1| = k$ and $|A_2| = n-k$ . Note that for each prime $p$ , the $k$ least $\nu_p$ must be in $A_1$ and the $n-k$ largest $\nu_p$ must be in $A_2$ . Here is the main claim about cloudy partitions:

Claim: Suppose we have two cloudy partitions $S$ and $T$ : let the $\text{lcm}$ set and the $\gcd$ sets be $(S_1,S_2)$ and $(T_1,T_2)$ , respectively. Then either $S_1 \in T_1$ or $S_2 \in T_2$ . In essence, there cannot exist two elements in different partitions in $S$ that "swap places" moving from $S$ to $T$ .

Proof: Proceed by contradiction, say the two swapped elements were $a$ and $b$ with $a \in S_1$ and $b \in S_2$ . Then as $a \neq b$ , for some prime $p$ $\nu_p(a) < \nu_p(b)$ so after swapping we arrive at a contradiction as some element in $T_1$ has greater $\nu_p$ than some element in $T_2$ .

This implies that starting with an initial $\text{lcm}$ set with one element and adding elements one at a time, we hit all possible cloudy partitions given optimal ordering. But notice that:

There must exist at most two partitions that share an equal GCD/LCM = $M$ , since either $M$ is in the GCD set or the LCM set. Note that it is impossible to add any other than $M$ from the GCD set to the LCM set whilst keeping $M$ equal.

If $M$ changes, then we require at least two elements to be added to the LCM set. We must move all of the elements with $\nu_p = \nu_p(M)$ (there must be at least one) as well as move one element with $\nu_p > \nu_p(M)$ for some prime $p$ to change $M$ .

All together, this means that we need $3 \cdot (1007+1)/2 = 3024$ elements to attain $2015$ cloudy partitions.

This post has been edited 1 time. Last edited by mathlogician, Feb 20, 2023, 12:08 AM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1745 posts

awesomeming327.

#24 h Apr 3, 2023, 4:29 AM • 2 Y

Y by CertifiedNoob, Pear222

Let the elements of $A$ be $a_1<a_2<a_3<\dots < a_n$ . Then, $\text{min}(A_1) \ge \text{lcm}(A_1) = \text{gcd}(A_2) \ge \text{max}(A_2)$ so $A_2$ is of the form $\{a_1,a_2,\dots, a_k\}$ and $A_1$ is $\{a_{k+1},a_{k+2},\dots ,a_n\}$ . Call $k$ spicy if $A_1$ and $A_2$ is a good partitioning.

$~$
For all of the following parts, we can define $0$ and $n$ as spicy and have no problems. Now, we'll show that $k$ , $k+1$ , $k+2$ cannot all by spicy. If so, let
$\begin{align*} d_1 &= \text{gcd}(a_1,\dots, a_k)=\text{lcm}(a_{k+1},\dots, a_n) \\ d_2 &= \text{gcd}(a_1,\dots, a_{k+1})=\text{lcm}(a_{k+2},\dots, a_n) \\ d_3 &= \text{gcd}(a_1,\dots, a_{k+2}) = \text{lcm}(a_{k+3},\dots, a_n) \end{align*}$ Then we deduce that $a_1,\dots a_k\mid d_1\mid a_{k+1}\mid d_2\mid a_{k+2}\mid d_3\mid a_{k+3},\dots, a_n$ so $d_2=a_{k+1}=a_{k+2}$ which is a contradiction. From here it is not hard to deduce that $n\ge 3024$ . Construction is omitted.

Z K Y

The post below has been deleted. Click to close.

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

1930 posts

#25 h Aug 3, 2023, 12:21 AM

Y by

I apologize for what you are about to read. (Alternatively, just don't read this and skip to the next, probably much better, solution.)

The answer is $\boxed{3024}$ . If $S=\{1,2,3\}$ , then $3024$ is achieved by
$A=S\cup 6S\cup 6^2 S\cup\dots\cup 6^{1007} S.$ The partitions all have every element in $A_1$ be less than every element in $A_2$ , so I will specify the partitions by the largest element of $A_1$ , and they are
$1,3,6,3\cdot 6,6^2,3\cdot 6^2,\dots,6^{1006},3\cdot 6^{1006},6^{1007}.$

Call the common lcm/gcd in the good partitions checkpoints. The intuition is that everything in $A_1$ divides the checkpoint and the checkpoint divides everything in $A_2$ . Let the checkpoints be $c_1<c_2<\dots<c_n$ .

A checkpoint $c$ is said to upwork if $c\in A$ and a good partition with $c$ being the checkpoint has $c$ belonging to $A_1$ .
A checkpoint $c$ is said to downwork if $c\in A$ and a good partition with $c$ being the checkpoint has $c$ belonging to $A_2$ .
A checkpoint $c$ is said to bothwork if $c$ both upworks and downworks.
A checkpoint $c$ is said to barely work if $c\not\in A$ .
A checkpoint $c$ is said to onework if it doesn't bothwork.
A checkpoint $c$ is said to directionally work if it oneworks but doesn't barely work.

Consider the elements of $A$ that are strictly between $c_i$ and $c_{i+1}$ . If $c_i$ upworks or barely works, they must have gcd $c_i$ , and if $c_{i+1}$ downworks or barely works, they must have lcm $c_{i+1}$ . In any of these cases, there must be at least two elements of $A$ strictly between $c_i$ and $c_{i+1}$ (since otherwise the gcd would be that element since it divides $c_{i+1}$ and the argument for lcm is similar). Call these two elements two sacrifices.

Note that a checkpoint that oneworks contributes $1$ to the good partition count while a checkpoint that bothworks contributes $2$ . However, each checkpoint that directionally works needs at least $2$ sacrifices, and each checkpoint that bothworks or barely works needs at least $4$ sacrifices, with at least $2$ in each direction.

Claim. Checkpoints that barely work are never optimal. That is, for every solution with a barely working checkpoint, there exists an equivalent or better solution.
Proof. If this barely working checkpoint is the least or greatest one, assume WLOG it is the least one. Then replace it with an only upworking checkpoint and remove the at least two sacrifices below it, which is better.
Otherwise, the least and greatest checkpoints are not barely working. Then remove this barely working checkpoint and $2$ of its sacrifices. If the greatest checkpoint upworks, just add the lcm of its sacrifices that are greater than it(they should not be multiples of each other since then their gcd is not the greatest checkpoint, so the lcm is not in $A$ yet), and if it doesn't upwork, then just add two sacrifices above it to make it bothwork.

Each sacrifice can be used for at most $2$ checkpoints. Therefore, there must be at least $\left\lceil\frac{2015}{2}\right\rceil=1008$ pairs of sacrifices, so there must be at least $2\cdot 1008=2016$ sacrifices.

Since each checkpoint contributes at most $2$ to the good partition count, there must be at least $\left\lceil\frac{2015}{2}\right\rceil=1008$ checkpoints. Therefore, in total, there are at least $2016+1008=3024$ elements in $A$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

8877 posts

#26 h Dec 2, 2023, 6:55 PM

Y by

The answer is $\boxed{3024}$ . In particular, I claim that we need at least $\frac 32(n+1)$ elements for general $n$ . Call a set $S$ good if there exists a good partition of $A$ with $S = A_1$ . Call the signature of a good partition the common GCD/LCM.

For construction, fix two primes $p, q$ , and consider the set $S = \{p^nq^{n-1}, p^{n-1}q^n, p^nq^n\}$ for $1 \leq n \leq 1008$ . To prove that this set works, arrange the elements of $S$ in increasing order and consider sets of the form $A_i$ consisting of the first $i$ elements. We can show that partitioning $S$ into $A_i$ and its complement for $i \equiv 0, 2 \pmod 3$ works. This yields $2015$ such sets (note that we cannot count $A_{3024}$ ).

For the bound, the key is the following claim:

Claim. If $S$ and $T$ are two good sets, then $S \subset T$ or $T \subset S$ .

Proof. Assume otherwise. Then, let $X = S \setminus T$ and $Y = T \setminus S$ . Note that every element in $S$ divides every element in $A \setminus S$ , so every element in $X$ divides every element in $Y$ . On the other hand, every element in $Y$ must also divide every element in $X$ by similar logic, which is an obvious contradiction. $\blacksquare$

Now, this means that we can characterize a superset of all good sets $X \in A$ by taking some set $X_0$ and inductively appending $a_i$ to $X_{i-1}$ to form $X_i$ . The final claim is the following:

Claim. Suppose that $X_i$ and $X_{i+1}$ are both good. Then $X_{i+2}$ is not good.

Proof. Let $a$ be the signature of $X_i$ . If $a_{i+1} = a$ , then the signature of $X_{i+1}$ remains $a$ . On the other hand, this means that $a \mid a_{i+2}$ ; say $a_{i+2} = ar$ .

Note that the signature of $X_{i+2}$ ought to be $ar$ , so $ar$ divides every element in $X_{i+2}$ ; this means it divides every element of $X_{i+1}$ too, so the signature of $X_{i+1}$ cannot be $a$ , contradiction!

If $a_{i+1} \neq a$ , we get a contadiction too similarly. $\blacksquare$

This bounds (say by Pigeonhole) the upper bound of valid $X_i$ to be $\frac 23(|A| - 1) +1$ , which yields the answer.

Z K Y

The post below has been deleted. Click to close.

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

198 posts

#27 h Feb 9, 2024, 9:41 AM

Y by

Answer: $3024$ .

Let $S$ be the set of $n$ elements with exactly $2015$ good partition. Let $a_1 < a_2 < \dots < a_n$ be the elements of $S$ . Let $S_1, S_2$ be an arbitrary partition. Then $\gcd(S_1) = \text{lcm}(S_2)$ , meaning $\max(S_2) \le \min(S_1)$ . Hence $S_1 = \{a_1, a_2, \dots, a_k\}$ , $S_2 = \{a_{k+1}, a_{k+2}, \dots, a_n\}$ for some $k \ge 1$ . Call an integer $1 \le k \le n-1$ special if $\{a_1, a_2, \dots, a_k\}$ and $\{a_{k+1}, a_{k+2}, \dots, a_n\}$ is a good partition. Then there are exactly $2015$ special integers. Let $i_1 < i_2 < \dots < i_{2015}$ be the special integers. Consider the following claim:

Claim: $x, x+1, x+2$ cannot be all special.

Proof. Assume the contrary, $x, x+1, x+2$ be all special integers for some $x$ . Then we have $\text{lcm}(a_1, a_2, \dots, a_x) = \gcd(a_{x+1}, a_{x+2}, \dots, a_n)$ , which means $a_i \mid a_{x+1}$ for all $1 \le i \le x$ . Thus $\gcd(a_{x+2}, a_{x+3}, \dots, a_n) = \text{lcm}(a_1, a_2, \dots, a_{x+1}) = a_{x+1}$ , so $\text{lcm}(a_1, a_2, \dots, a_{x+1}, a_{x+2}) = a_{x+2} = \gcd(a_{x+3}, a_{x+4}, \dots, a_n)$ . Hence $a_{x+1} = \gcd(a_{x+2}, a_{x+3}, \dots, a_n) = a_{x+2}$ , a contradiction. $\blacksquare$

The above claim implies $i_{k+2} - i_k \ge 3$ . Note that $i_{2015} \neq n$ , so $n > i_{2015} \ge i_{2013} + 3 \ge i_{2011} + 6 \ge \dots \ge i_1 + 3 \cdot 1007 \ge 1 + 3 \cdot 1007$ . Therefore $n \ge 2 + 3\cdot 1007$ . If $n = 2 + 3 \cdot 1007$ , then the above inequalities must be all equalities, which means $i_1 = 1$ . Then note that $i_2 \neq 2$ , so $i_2 \ge 3$ . Therefore $3 \cdot 1007 = n - 2 \ge i_{2014} \ge i_{2012} + 3 \ge \dots \ge i_2 + 3 \cdot 1006 \ge 3 \cdot 1007$ , therefore $i_{k+2} = i_{k} + 3$ for all $k$ . Thus we can easily see that $i_{2014} = n-2, i_{2015} = n-1$ , which is an evident contradiction. Therefore $n \neq 3 \cdot 1007 + 2$ , so $n \ge 3 \cdot 1007 + 3 = 3024$ . Construction for $n = 3024$ is below:

$\{3, 3 \cdot 2, 3^2, 3^2 \cdot 2, 3^2 \cdot 2^2, 3^3 \cdot 2, \dots, 3^{1008} \cdot 2^{1007}, 3^{1008} \cdot 2^{1008}, 3^{1009} \cdot 2^{1007}\}$ satisfies the condition. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

3373 posts

#28 h Aug 1, 2024, 12:27 AM

Y by

The answer is $3024$ , with the construction being omitted. Let $A = \{a_1, a_2, \dots, a_n\}$ with $a_1 < \cdots < a_n$ . Clearly we must have $A_1 = \{a_1, \dots, a_i\}$ and $A_2 = \{a_{i+1}, \dots, a_n\}$ for some good index i. We make the following key claim:

Claim: $\{i, i+1, i+2\}$ cannot all be good.

Proof. For the sake of contradiction, assume all three indices are good. We have $\operatorname{lcm}(a_1, \dots, a_i) \mid a_{i+1} = \operatorname{lcm}(a_1, \dots, a_{i+1}) = \operatorname{gcd}(a_{i+2}, \dots, a_{n})$ But $\operatorname{lcm}(a_1, \dots, a_{i+1}) \mid a_{i+2} = \operatorname{lcm}(a_1, \dots, a_{i+2}) = \operatorname{gcd}(a_{i+3}, \dots, a_{n}) = \operatorname{gcd}(a_{i+2}, \dots, a_{n})$ so $a_{i+1} = a_{i+2}$ , contradiction.

Claim: $\{1, 2\}$ cannot both be good, and likewise, $\{n-2, n-1\}$ cannot both be good

Proof. Assume $1, 2$ are both good. Now clearly this means $a_1 = \operatorname{gcd}(a_2, \dots, a_n) \implies a_1 \mid a_2$ and $\operatorname{lcm}(a_1, a_2) = a_2 = \operatorname{gcd}(a_3, \dots, a_n)$ which implies $a_1 = a_2$ , contradiction. An identical argument can be made for the latter part.

Now if $n < 3024$ then there is at most $\tfrac{2(n-5)}{3} + 2 \le 2014$ good indices, and therefore partitions, so 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.

183 posts

#29 h Apr 4, 2025, 8:02 AM • 1 Y

Y by L13832

Answer is $3034$
Claim: If $a_i$ and $a_j$ belong to $A_1$ and $A_2$ respectively then $a_i < a_j$
Since $a_i \leq LCM ( a_i , \dots ) = GCD (a_j , \dots ) \leq a_j$ , but since $a_i$ and $a_j$ are distinct it follows that $a_i < a_j$ .
Let $A = ({a_1, \dots, a_n})$ be a set with 2015 good partitions, where $a_1 < a_2 < \dots < a_n$
Let an element $a_ i$ of A be called amazing if the paritition into the sets $({a_1,\dots a_i })$ and $({a_{i+1}, \dots , a_n})$ is good
Claim: $a_1$ and $a_2$ , cannot be both amazing.
FTSOC assume they are,
$a_1 = GCD (a_2, \dots , a_n) \implies a_1 \mid a_2$ $LCM (a_1,a_2) = a_2 = GCD (a_3, \dots , a_n) \implies a_1 = a_2$ A contradiction

Claim: If $a_i$ and $a_{i+1}$ are amazing then $a_{i+2}$ cannot be amazing
FTSOC assume it holds
We have that $LCM(a_1, \dots a_i) = GCD(a_{i+1} , \dots, a_n) \implies LCM(a_1, \dots a_i) \mid a_{i+1}$ $LCM(a_1, \dots a_{i+2}) = GCD(a_{i+3} , \dots, a_n) \implies a_{i+2} \mid a_{i+3} , a_{i+4}, \dots , a_n$ $LCM(a_1, \dots a_{i+1} ) =a_{i+1} = GCD(a_{i+2} , \dots, a_n) = a_{i+2}$ A contradiction
Since every amazing number is the largest element of Set $A_1$ of a good partition. Now, to have $2015$ good sets we require to have $2015$ amazing numbers.
From this we can see that $n \geq 3033$
Claim: $n=3033$ is not possible
FTOSC assume it works.
Then we have that $a_{3032}$ is the last amazing number, and $a_{3031}$ is also an amazing number.
$LCM(a_1, \dots, a_{3031}) = GCD(a_{3032} , a_{3033} )$ $LCM(a_1, \dots, a_{3032}) = a_{3032} = GCD( a_{3033} )= a_{3033}$ A contradiction
Construction for $n=3034$
If $a_{A-1}$ and $a_A$ is an amazing numbers then $a_{A+1} = (a_A) p$ , where $p$ is a prime which does not divide any $a_i$ where $i \leq A$
$a_1 = 1 , a_2 = p_1 , a_3 = p_2, a_4 = p_1p_2$
Here the amazing numbers are $a_1, a_3, a_4 ,a_6,a_7, \dots , a_{3031},a_{3032}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a