### alexwice's blog

By alexwice, history, 23 months ago,

Construct A Rectangle

A Editorial

Berland Music

B Editorial

Set or Decrease

C Editorial

Shuffle

D Editorial

Math Test

E Editorial

 » 23 months ago, # | ← Rev. 2 →   +36 For problem F, here's another proof that the answer is at least $n-3$: SpoilerFor a number $x=\prod_{i} p_i^{\alpha_i}$, let $f(x) = \prod_i p_i^{\alpha_i \bmod 2}$. Then $x$ is a perfect square if and only if $f(x) = 1$.Note that for any numbers $x,y$, we have $f(xy) = f(f(x)f(y))$, and furthermore, $f(x^2y) = f(y)$. It shows that $f(n! \cdot (n+1)!) = f((n!)^2 \cdot (n+1)) = f(n+1)$.Assume that $n=2k$ is an even number. If we choose all the numbers from $[1,n]$, we will get $f(1! \cdot 2! \cdot \cdots \cdot (2k-1)! \cdot (2k)!) = f(2 \cdot 4 \cdot \dots \cdot (2k)) = f(2^k \cdot k!)$. When $k$ is an even number. Then we have $f(2^k \cdot k!) = f(k!)$. It means if we remove the number $k$ from the subset $S$ we choose, we will have $f(S) = 1$, so there's always a subset of size $n-1$ that satisfy the conditions. So in this case, we have $|S| \geq n - 1$ When $k$ is an odd number, Then we have $f(2^k \cdot k!) = f(2) \cdot f(k)$. Similarly, we can just remove number $2$ and number $k$, and it will got $f(S) = 1$. In this case, $|S| \geq n-2$ From the above, we can always find a solution of size at least $n-2$ for an even number of $n$. When $n=2k+1$ is an odd number, we can just ignore the number $n$, and follow the above construction. We ignored one number, and we threw at most $2$ numbers, so we can always find a set that contains at least $n-3$ numbers.
•  » » 23 months ago, # ^ | ← Rev. 3 →   +3 Thanks. I have thought F for a long time but I can't solve it. Thanks for your proof.And I wonder that why you consider that $answer\ge n-3$. In another words, why do you think that the answer is so large like this?Thanks in advance.