, 
lies on 
When 
,
is increasing or decreasing
Prove that for any positive number 
,
of the set ![$[n]=\{1,2, \dots, n\}$](http://latex.artofproblemsolving.com/8/f/e/8fea25e7cf72aabc60f48c3b30f4d4818a084ae3.png)
and keeps it hidden from Bob. In a move, Bob tells Alice a permutation 
of ![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
,![$i \in [n]$](http://latex.artofproblemsolving.com/e/6/7/e67206e47d5d5875105b339f177a3ab8f5151a5e.png)
such that 
.
moves.
,
be a point on the segment 
and let 
be the intersection point of 
with the diagonal 
.
at point 
.
be a point on the segment 
such that 
.
be the intersection point of the diagonal 
and the segment 
.
and 
are concyclic.
bigger than 
water if the last four digit is 
.
be a positive integer. Prove that![\[
\underbrace{99\dots 99}_{k-1}4\underbrace{00\dots 00}_{k-1}9
\]](http://latex.artofproblemsolving.com/2/f/c/2fc13c37764c96401d76f6288476d7372c17435b.png)
can't be a prime number.
be a positive integer. Solve over 
,![\[
x^2+2x-3\underbrace{99\dots 99}_{2m}.
\]](http://latex.artofproblemsolving.com/5/4/d/54d311ebb1f6d92ffc1d2b8f4d6d5de225b349e9.png)
be the set of positive integers less than 
?
or 
,
with 
and 
and 
.
solutions to 
and 
solutions to 
,
and 
,
and 
.
and 
solutions, respectively.
and four solutions to 
.
where 
is a monic polynomial of degree 
satisfying 
where 
and 
,
and 
if polynomial 
such that 
Evaluate 
and 
where 
denotes greatest integer function.
,
.
.
![\[
\sqrt{x-3}+\sqrt{6-x} \leq p
\]](http://latex.artofproblemsolving.com/3/2/b/32b8bf5c8aa4d7561933e38ee0e2a0480e1a2f07.png)
In which 
,
.
Y by quangminhltv99, Davi-8191, tenplusten, qubatae, NTSQWER, Adventure10, NicoN9, taki09
For a finite set 
of positive integers, a partition of into two disjoint nonempty subsets 
and 
is 
if the least common multiple of the elements in is equal to the greatest common divisor of the elements in . Determine the minimum value of 
such that there exists a set of positive integers with exactly 
good partitions.
of positive integers, a partition of into two disjoint nonempty subsets 
and 
is 
if the least common multiple of the elements in is equal to the greatest common divisor of the elements in . Determine the minimum value of 
such that there exists a set of positive integers with exactly 
good partitions.This post has been edited 5 times. Last edited by va2010, Jul 8, 2016, 7:04 PM
.
is a cloudy partition, then 
.
to be the minimum value of 
where 
to be the same minimum value of 
,
.
.![\[ g(k+1) = f(k)+2\hspace{4mm}\text{and}\hspace{4mm}f(k+1) = \min(g(k)+1,f(k)+2) \]](http://latex.artofproblemsolving.com/1/4/5/1458981b7204727506386facd2a7deff3174a600.png)
and it is easy to calculate 
.
minimized. Then there is a bijection between the cloudy partitions of 
is a cloudy partition of 
is a cloudy partition of 
is a cloudy partition of 
is a cloudy partition of 
,
divides every element in 
must contain 
,
satisfying the conditions. Consider the cloudy partition of 
,
,
implies 
,
,
.
with 
.
and take 
.
satisfying the conditions. Consider the cloudy partitions of 
,
and hence 
.
,
,
.
.
,
,
.
,
.
be the midpoint of the good partition with smallest midpoint. Then 
for some integer 
for the 
in 
we have 
.
be the second-smallest midpoint, and note that 
because it is greater than 
then we have 
remaining the same except for 
where 
is the third-smallest midpoint. If 
,
because if so, the LCM of the new 
but if the GCD of the new 
contradicting 
,
divides all of 
and is also a multiple of 
,
for some 
.
is not one of the 
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 
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 \}.\]](http://latex.artofproblemsolving.com/3/7/7/37700e7f44f56fb9aa2b59a6afdb4c7c34032984.png)
where 
.
and similar for lcm. Note that any partition must be of the form 
and 
.
be those values of 
.
must divide all elements greater than 
and 
.
,
and so on. Then basically the problem reduces to this: we have 2016 disjoint sets 
where 
for all 
.
,
sets with size 1, and hence the total sum of sets is at least 
.
.
where 
(by construction), and otherwise 
.
doesn't divide 
so we don't introduce any other additional partitions here.
be the set of numbers less than or equal to 
and 
is good.
that are nice. Then gcd
)
.
,
dividing the numbers bigger than 
,
.
,
,
with two blocks of a single nice number. We first need 
numbers that are not nice between blocks, thus having 
for previous case and 
.
Let 
be numbers that are not nice and 
the opposite, we get something like 
.
.
,
and 
for some 
.
and 
.
.
are both good, then 
.
and 
.
,
.![\[d_k=\gcd(\mathrm{lcm}(d_k,a_{k+1}),a_{k+1}).\]](http://latex.artofproblemsolving.com/b/3/4/b34cc648bcc7a9d78f591a20cc7bbc0fcadf9751.png)
Let 
and 
where 
.
.
,
,
,
,
.
,
,
all be good. Also the lemma implies that we can't have both 
be good, since the lemma would imply 
,
,
.
all be distinct primes. The construction goes as follows. Let 
,
,
where we define 
.![\[p_1,q_1,p_1q_1,p_1q_1p_2,p_1q_1p_2,p_1q_1p_2q_2,\ldots.\]](http://latex.artofproblemsolving.com/8/0/9/8090963dab0aa9b9aaa7f2a203df28779551cbdc.png)
Here, 
.
are two sets of integers, I say that 
if 
.
.
.
,
and 
,
and 
,
and 
,
,
,
,
.
,
.
is a good partition of the set 
.
,
.
is split between the two parts of the partition (if no 
,
,
.
,
,
as 
,
of the first set is 
,
,
of 
since 
.
.
should alternate between 1 and 2, which gives 
to be minimum.
,
.
.
Let 
where 
Notice that if a partition 
is good, then 
That is, the partition must look like 
partitions 
,
,
,
Notice that 
so 
for all elements 
Similarly, 
It thus follows that 
if 
and 
However, it follows from 
for all 
so 
Similarly, 
Therefore, if 
but this would imply that 
,
and 
cannot be good partitions, since this would force 
and neither can 
,
elements in 
We will now provide a construction. WLOG let 
for 
From here on out, 
and 
are both good. Let 
,
,
,
,
,
,
and 
which can be easily seen to work. 
To show that this is achievable, consider the set 
and 
for 
where the 
are distinct primes. It is easy to see that this works.
Consider a good partition such that 
we cannot have 
so there does not exist a good partition of 
and 
Let 
be the sets 
and let 
be all the sets 
must be a subset of 
for all 
and 
must both be 
Let 
Then 
This means that the gcd of all elements of 
must be 
Furthermore, all elements of 
divide 
so 
But this means that 
which means that it is also the lcm of the elements of 
so the element of 
must equal 
and 
are both 
and 
Then we must have that 
so 
But then 
a contradiction. 
then 
for 
and let 
and 
Then 
must divide all elements of 
It follows that 
Then the gcd of all elements of 
must also be 
However, 
divides all the elements of 
and all elements of 
divide 
This means that the lcm of all the elements of 
must be at most 
so 
However this is a contradiction since 
and 
Thus, the claim is proven. 
for 
Finally, we must have that the total number of elements is 
as desired.
Cloudy partitions above have been colored red.
.
is decisive if a cloudy partition is 
.
,
may not all be decisive.![\[\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).\]](http://latex.artofproblemsolving.com/7/9/d/79d1e610ccb6e9a7154bc789b9053fc9efd5c4f2.png)
However, from ![\[s_k=\operatorname{lcm}(s_1,\ldots,s_k)=\gcd(s_{k+1},\ldots,s_n)=s_{k+1},\]](http://latex.artofproblemsolving.com/d/1/0/d10e635ecd9acde5c2f6bd6f50c2a2bd104050d9.png)
contradiction. 
and 
may not both be decisive.)
,
,
,
,
is 3024.
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 
be the elements of 
and 
cannot both be clouds.
and 
.
,
.
a contradiction. We can use a similar argument to prove that 
,
cannot both be clouds.
.
.
and 
.
,
.
.
for some 
.
,
after 
if this partition results in 
.
.
,
.
,
.
,
,
,
.![\[ 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\]](http://latex.artofproblemsolving.com/d/d/a/ddabc59b28b5049207984871b616370b1ebf3eab.png)
In general, we have the repeating 3-pattern of 
.
and 
.
,
,
makes the dividers easy to handle.
,
.
Note all 
,
.
.
,
.
.
.
(since 
,
,
.
.
.
,
,
is necessary. So see its sufficient, for primes 
consider
where all blue numbers are good. 
for 
.
,
.
for some 
denote this partition for each 
.
are all good partitions. Then we notice that 
all divide 
.
and 
.
and 
,so 
,
and 
can also not both be good), so for 
,
partitions, which implies 
for each positive integer 
works.
and 
.
must be in 
largest 
:
and 
,
or 
.
and 
.
,
so after swapping we arrive at a contradiction as some element in 
has greater 
.
(there must be at least one) as well as move one element with 
for some prime 
elements to attain 
.
so 
and 
.
and 
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\]](http://latex.artofproblemsolving.com/d/0/a/d0a144d4621199d01d69a5f8d3e7c8f73f25fa71.png)
so 
which is a contradiction. From here it is not hard to deduce that 
.
,![\[A=S\cup 6S\cup 6^2 S\cup\dots\cup 6^{1007} S.\]](http://latex.artofproblemsolving.com/a/4/f/a4f65d1cae6c72ae5471d16053e7cfad037fb082.png)
The partitions all have every element in ![\[1,3,6,3\cdot 6,6^2,3\cdot 6^2,\dots,6^{1006},3\cdot 6^{1006},6^{1007}.\]](http://latex.artofproblemsolving.com/d/7/c/d7c3c8c92e4fc386f3a0342e425f02f2770382e7.png)
.
and a good partition with 
.
and 
.
pairs of sacrifices, so there must be at least 
sacrifices.
elements in 
elements for general 
.
,
for 
.
consisting of the first 
works. This yields 
)
or 
.
and 
.
,
.
by taking some set 
and inductively appending 
to form 
.
are both good. Then 
is not good.
,
;
.
,
,
,
be the elements of 
be an arbitrary partition. Then 
,
.
,
for some 
.
special if 
and 
is a good partition. Then there are exactly 
be the special integers. Consider the following claim:
cannot be all special.
,
for all 
.
,
.
,
.
,
.
.
,
.
,
.
,
for all 
,
,
.
is below:
satisfies the condition. 
with 
.
and 
for some good index i. We make the following key claim:
cannot all be good.
But 
so 
,
cannot both be good, and likewise, 
cannot both be good
are both good. Now clearly this means 
and 
which implies 
,
then there is at most 
good indices, and therefore partitions, so we are done.
belong to 
,
and 
.
be a set with 2015 good partitions, where 
of A be called amazing if the paritition into the sets 
and 
is good
and 
, cannot be both amazing.
A contradiction
are amazing then 
cannot be amazing
A contradiction
good sets we require to have 
is not possible
is the last amazing number, and 
is also an amazing number.
A contradiction
and 
is an amazing numbers then 
, where 
is a prime which does not divide any 
necessary divider slots, or ![\[A = \{1 \cdot (pq)^k, p \cdot (pq)^k, q \cdot (pq)^k\}, ~ 0 \leq k \leq 1007\]](http://latex.artofproblemsolving.com/c/a/d/cad919aa566a4989151e3b1e545e88be826190f5.png)
![\[p^0q^0 ~ {\color{red} \mid} ~ p^1q^0 ~~ p^0q^1 ~ {\color{red} \mid} ~ p^1q^1 ~ {\color{red} \mid} ~ p^2q^1 ~~ p^1q^2 ~ {\color{red} \mid} ~ p^2q^2 ~ {\color{red} \mid} ~ p^3q^2 ~~ p^2q^3 ~ {\color{red} \mid} ~ p^3q^3 ~ {\color{red} \mid} ~ \ldots\]](http://latex.artofproblemsolving.com/3/7/4/374138bb096259492fe066dd1b6372ee56837687.png)
