Y by Smita, dwip_neel, samrocksnature, megarnie, jhu08, son7, Iora, mathmax12, Adventure10, Mango247
A permutation of the set of positive integers ![$[n] = \{1, 2, . . . , n\}$](//latex.artofproblemsolving.com/4/f/f/4ff58e6e89a225ffa8db0ab50038fdadd9d4e2bc.png)
is a sequence 
such that each element of ![$[n]$](//latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
appears precisely one time as a term of the sequence. For example, 
is a permutation of ![$[5]$](//latex.artofproblemsolving.com/c/4/2/c4216c69e041fca0904e8c5366d4480d1b2ca8b8.png)
. Let 
be the number of permutations of for which 
is a perfect square for all 
. Find with proof the smallest 
such that is a multiple of 
.
![$[n] = \{1, 2, . . . , n\}$](http://latex.artofproblemsolving.com/4/f/f/4ff58e6e89a225ffa8db0ab50038fdadd9d4e2bc.png)
is a sequence 
such that each element of ![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
appears precisely one time as a term of the sequence. For example, 
is a permutation of ![$[5]$](http://latex.artofproblemsolving.com/c/4/2/c4216c69e041fca0904e8c5366d4480d1b2ca8b8.png)
. Let 
be the number of permutations of for which 
is a perfect square for all 
. Find with proof the smallest 
such that is a multiple of 
.This post has been edited 2 times. Last edited by tenniskidperson3, Dec 22, 2015, 2:55 AM
Reason: Lolol latex was wrong for 5 years and nobody caught it
Reason: Lolol latex was wrong for 5 years and nobody caught it
can be uniquely written as 
,
is square-free (for example 
)
must obviously be of the same form if 
)
the relation 
if and only if 
is a perfect square. Clearly 
is reflexive, symmetrical, and transitive, therefore an equivalence relation. Therefore a permutation 
has the required property if and only if 
for all 
.
be 
;
in the same class, so there will be 
ways to do it. If there are 
classes, of cardinalities 
,
of such permutations is therefore 
.
,
we need at least one 
.
will do; moreover, then 
.
is the most numerous, so it is necessary to have 
,
.
,
.
.
permutations.
.
contains a factor of 67, and it is also obvious that the minimum of n will thus occur when 
where no square number (except 
obviously) divides 
is also of the same form.
to always be a square.
,
a subset of 
?
isn't listed - and in fact it isn't a part of BOGTRO's partition. Each of the parts of the partition is the set of all terms of the form 
where 
the product should be over all square-free integers 
I would still like to know if I am the only one that felt it was worded weird..
ways
ways
ways
,
and 
.![\[1c, 4c, \dots, k^2c \]](http://latex.artofproblemsolving.com/6/9/c/69cd648c550acee2a99d0bf10baca74b8fea8582.png)
such that 
can be freely permuted around. Thus, we are able to define a formula for ![\[\prod_{c}\left\lfloor\sqrt{\frac{n}{c}}\right\rfloor!\]](http://latex.artofproblemsolving.com/e/7/c/e7c51fa7b49ac6d2e64a8bc0db99b7311f205749.png)
,![\[\lfloor \sqrt{n} \rfloor \ge 67 \implies n \ge 67^2 = 4489.\]](http://latex.artofproblemsolving.com/e/f/5/ef51c7cfbf6524376a8c6dca69f4f815ae041772.png)
does indeed work when substituted, thus being the answer.
share the same ``radical part" (i.e. 
where 
)
positive integers at most ![\[P(n)=\prod_{\text{squarefree }k}\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor!.\]](http://latex.artofproblemsolving.com/e/1/d/e1d99189240d995cf03b4ee37369109d26c82325.png)
Since 
,
,
for some squarefree 
,
be the set of squarefree numbers. Moreover, for any 
let 
be the number of positive integers 
where 
is a square number. We explicitly give the formula ![\[ P(n) = \prod_{s \in S} f_s(n)! \]](http://latex.artofproblemsolving.com/a/f/b/afb442030f2176a3a9602265be25c76996f7f1f2.png)
Note that if 
.
then 
,
then 
.
.
so we are done
We will find an explicit formula for 
Write 
where 
:
those of the form 
those of the form 
and so on, for every squarefree integer. If 
is the 
the set of integers of the form 
Clearly each number in each category must be paired with itself in our final result. In particular, there are 
numbers in the 
Therefore,![\[
P(n) = \prod_{i=1}^{\infty} \left\lfloor \sqrt{\frac{n}{m_i}} \right\rfloor !.
\]](http://latex.artofproblemsolving.com/5/3/7/5373189eaeb6d0d69fcc0c17b885dc8bd643dcba.png)
Note that 
so one of the terms has to be 
if 
since any other term would result in a larger value of 
This works since 
denote the set of squarefree integers. Then ![\[\prod_{k \in S} \left \lfloor \sqrt{\frac nk} \right \rfloor !.\]](http://latex.artofproblemsolving.com/4/1/7/41787a855034b9fce269f4440820a8c4d68c2dc2.png)
,
and 
,
ways so far (as there are 
perfect squares in our allowed range).
times a perfect square, or 
for some 
,![\[\prod_{1\le \ell\le n}\left\lfloor\sqrt{\frac{n}{\ell}}\right\rfloor!\qquad \text{for all squarefree $\ell$.}\]](http://latex.artofproblemsolving.com/d/9/1/d91b1e19579638e2650cbea0c6c0a645ad8cad3c.png)
Since 
,
’
,
,
.
for some positive integer 
that can be expressed as 
for some positive integer 
.
if and only if 
for some 
.
.
,
,![\[m=\Pi_{b\leq n} |S_{(n,b)}|!,\]](http://latex.artofproblemsolving.com/4/2/3/4230f5451358cc00e2666ee475331443e1038a3c.png)
for all 
,
.
,
,
,
for some ![\[|S_{(n,b)}|\geq 67 \iff n\geq 67^2b \iff n\geq 4489,\]](http://latex.artofproblemsolving.com/f/c/5/fc580ad222708a6e7323bd6d7609a26fc71bb539.png)
since 
.
;
;
,
permutations 
,
as the set of positive integers at most 
where 
Every integer in 
belongs to some 
All 
and 
where 
and 
are distinct squarefree integers. Then for some integers 
,
we have 
implying 
is a square. By a simple 
argument it is easy to see that the latter can only occur when 
,
If 
is a square if and only if some 
.
and 
where 
is a square, which implies 
.
,
.
works since 
.
,
and generalizing this obvious statement. We then split the numbers into groups based on their largest squarefree factor 
We need a factor of 
and each of these squares match with such a 
there are 
Clearly for 
it must be a multiple of 
Thus to minimize 
We can then see that clearly 
works, so this is our answer.
goes to the position of 
,
can be permuted amongst themselves.(where a doesn't change for making permutations possible and a is a non-square number)
(
are the numbers with a=2)
Number of 
)
will still result in a valid sequence, and this applies for all squarefree numbers. We arrive at this conclusion from noting that all squares are permutable with each other, and then all values 
where 
is the 
-
.
