ISL 2023 A7
問題
$ N$を正の整数とする。$ (1, \cdots, N)$の並べ替え$(a_1, \cdots ,a_N),(b_1, \cdots,b_N),(c_1, \cdots ,c_N)$であって任意の整数$ 1 \leq k\leq N$において
$$\left|\sqrt{a_k}+\sqrt{b_k}+\sqrt{c_k}-2\sqrt{N}\right|<2023$$
が成り立つものが存在することを示せ。
考察と証明
$2023$という数字は多分割となんでも良さそう。$ N$が特別な場合のとき示せたりしないかな？例えば平方数のときとか？
不等式だから$ \sqrt{a_k} $を近似して評価してみるのが良さそうな気がする。割とガバガバでも大丈夫なはず。例えば小数第一位で四捨五入した整数値とか。四捨五入で考えてみる。$ \sqrt{1} ,\sqrt{2}, \sqrt{3} ,\sqrt{4} ,\sqrt{5} ,\sqrt{6}, \sqrt{7} ,\sqrt{8}, \sqrt{9}, \sqrt{10}, \sqrt{11} ,\sqrt{12} ,\sqrt{13} , \cdots $を四捨五入した値は$1,1,2,2,2,2,3,3,3,3,3,3,4 ,\cdots $
となり$n$が$2n$回現れる。$ N=n(n+1)+m\quad 0\leq m\leq 2n+1$とし、$ \sqrt{a_k}$を小数第一位で四捨五入した値を$A_k $とすれば$ (A_1,A_2, \cdots A_{n(n+1)+m})$は$(1,1,2,2,2,2, \cdots ,n+1)$の並び替えとなる。ただし、$ 1\leq i\leq n$において$i$は$2i$回現れ、$ n+1$は$m$回現れる。上の$ A_k$のような並び替えを良い並び替えと呼ぶことにする。$ \left|\sqrt{a_k}-A_k\right| < \dfrac{1}{2} $であるから、以下を示せば十分である。
良い並び替え$(A_1, \cdots ,A_{N}),(B_1, \cdots ,B_{N}),(C_1, \cdots ,C_{N}) $が存在して任意の整数$ 1 \leq k\leq N$に対して$\left|A_k+B_k+C_k-2\sqrt{N}\right|<2023- \dfrac{3}{2}$が成り立つ。
とりあえず$ m=0$の場合を考えてみる。以下が示せないか考える。
定数$c$と良い並び替え$(A_1, \cdots ,A_{n(n+1)}),(B_1, \cdots ,B_{n(n+1)}),(C_1, \cdots ,C_{n(n+1)}) $が存在して任意の整数$ 1 \leq k\leq n(n+1)$に対して$ \left|A_k+B_k+C_k-2 \sqrt{n(n+1)}\right|< c $
が成り立つ。$ \cdots (i)$
$ 2\sqrt{n(n+1)} $の値は$2n+1$に近いから任意の$k$で$ A_k+B_k+C_k=2n,2n+1,2n+2$あたりにならないかなと考えてみる。とりあえず実験してみる。例えば$n=4$を考える。
| $k=$ | $1,2$ | $3,4$ | $5,6$ | $7,8,9,10$ | $11,12,13,14$ | $15,16,17,18$ | $19,20$ |
|---|---|---|---|---|---|---|---|
| $ A_k$ | $1$ | $4$ | $4$ | $4$ | $2$ | $3$ | $3$ |
| $ B_k$ | $4$ | $1$ | $4$ | $3$ | $4$ | $2$ | $3$ |
| $ C_k$ | $4$ | $4$ | $1$ | $2$ | $3$ | $4$ | $3$ |
上のように$n=4$のとき任意の$k$で$ A_k+B_k+C_k=2n+1$となるようにとれる。$n$が他の場合を実験しても同様になるので任意の$n$で上のようになる？もう少し上の実験を眺めてみると$ a+b+c=2n+1$かつ$ 1\leq a,b,c \leq n$となる整数の組$(a,b,c)$が全て網羅していることに気づいた。実験の気づきから以下の補題を考える。
$a+b+c=2n+1$かつ$ 1\leq a,b,c \leq n$となる整数の組$(a,b,c)$を$ (a'_1,b'_1,c'_1), \cdots ,(a'_t,b'_t,c'_t)$とすると$ t= \dfrac{n(n+1)}{2} $かつ$ (a'_1, \cdots ,a'_t)$は$(1,2,2, \cdots ,n)$の並び替えである。ただし$ 1 \leq i\leq n$において$i$は$i$回現れる。$ b'_k,c'_k$についても同様。
対称性より$ a'_k $のみ示せばよい。
$ n+1 \leq a+b$でなければ$c$が存在しない。逆にそれを満たすなら$c$がただ$1$つに決まるので$ n+1 \leq a+b$かつ$1 \leq a,b\leq n$を満たす$(a,b )$ついて考える。$ n+1-a \leq b \leq n $であるがそれを満たす$b$の個数は$a$個であることがすぐに分かるので補題を得る。
良い並び替え$(A_1, \cdots ,A_{n(n+1)}),(B_1, \cdots ,B_{n(n+1)}),(C_1, \cdots ,C_{n(n+1)}) $が存在して任意の整数$ 1 \leq k\leq n(n+1)$に対して$ A_k+B_k+C_k=2n+1$が成り立つ。
$ a'_k , b'_k , c'_k $を補題$1$の並び替えとする。任意の正の整数$ 1 \leq k\leq \dfrac{n(n+1)}{2} $に対して$ A_{2k-1}=A_{2k}=a'_k$とし、$ B_k ,C_k $についても同様にすると補題$1$から明らかに条件を満たすので証明は完了した。
$ \left|2n+1-2 \sqrt{n(n+1)}\right|<1 $であるから補題$2$より$(i)$は$c=1$で条件を満たす良い並び替え$(A_1, \cdots ,A_{n(n+1)}),(B_1, \cdots ,B_{n(n+1)}),(C_1, \cdots ,C_{n(n+1)}) $が存在する。
これで$m=0$の場合は証明できたのでそれを用いて$ m$が全ての場合で証明する。以降$m≠0$とする。とりあえず実験。$n=4,m=7$の場合で実験してみる。$(A_1, \cdots ,A_{27})$は$(1,1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5)$の並び替えである。$m=0$の場合を使いたいのでこの$ 1$から$5$の数列から$7$個の数字を取り除いて上手くできないか考えてみる。$ \left|3A-2 \sqrt{N}\right| $が小さくなるような$ A$を考えることで$ (3,3,3,3,3,3,4)$を取り除いてみる。すると$(1,1,2,2,2,2,4,4,4,4,4,4,4,5,5,5,5,5,5,5)$となる。これを$m=0$のパターン$(1,1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4) $
に対応させると以下の表になる。
| $k=$ | $1,2$ | $3,4$ | $5,6$ | $7,8,9,10$ | $11,12,13,14$ | $15,16,17,18$ | $19 $ | $20$ |
|---|---|---|---|---|---|---|---|---|
| $ A_k$ | $1$ | $5 $ | $5 $ | $5 $ | $2$ | $4$ | $4$ | $5$ |
| $ B_k$ | $5$ | $1$ | $5$ | $4$ | $5$ | $2$ | $4$ | $5$ |
| $ C_k$ | $5$ | $5$ | $1$ | $2$ | $4$ | $5$ | $5$ | $4$ |
取り除いた$ (3,3,3,3,3,3,4)$に関しては$ (A_k,B_k,C_k)=(3,3,3),(3,3,4),(3,4,3),(4,3,3)$で満たすのでこのように構成することで、条件を満たすようにできそうだ。(感覚的な話だが、$n(n+1)$以上ある要素に対して高々$2n+1$しか取り除いてないので誤差はそこまで生まれないだろうという考え。)
一般化する。
・$ \dfrac{2}{3} \sqrt{N} $を小数第一位で四捨五入した値を$ M_N$とする。
・$ (1,1,2,2,2,2, \cdots ,n+1)$という$ 1 \leq i\leq n$において$ i$が$2i$回現れ、$n+1$が$m$回現れるもののうち小さい順に並んだものを$ P_N$とし$ P_N$から$ M_N$以上で小さい順に$m$個を取り除いたものを$ P'_N$とする。
・補題$2 $を満たすような並び替えを$(A'_1, \cdots ,A'_{n(n+1)}),(B'_1, \cdots ,B'_{n(n+1)}),(C'_1, \cdots ,C'_{n(n+1)}) $とする。
・$ (1, \cdots ,n(n+1))$の並び替え$ (i_1, \cdots ,i_{n(n+1)})$を$A'_{i_1 } \leq \cdots \leq A'_{i_{n(n+1)}}$とし、$ (f_N(A'_1), \cdots ,f_N(A'_{n(n+1)}))$を$ P'_N$の並び替えかつ$ f_N(A'_{i_1}) \leq \cdots \leq f_N(A'_{i_{n(n+1)}})$となるように定義する。$ (f_N(B'_1), \cdots ,f_N(B'_{n(n+1)})), (f_N(C'_1), \cdots ,f_N(C'_{n(n+1)}))$についても同様に定義する。
$ P_N$の$ M_N$以上で小さい順の$m$個の数は$ M_N$と$ M_N+1$のみである。
$ P_N$において$ M_N$は$ 2M_N$個、$ M_N+1$は$ 2(M_N+1)$個ある。$ M_N$以上の小さい順$ m$個に$ M_N+2$があると仮定すると$ 2M_N+2(M_N+1)< m$であるが$ \left| \dfrac{2}{3} \sqrt{N}-M_N \right|< \dfrac{1}{2} $より、
$ \dfrac{8}{3}n + \dfrac{4}{3} <4 ( \dfrac{2}{3} \sqrt{N}- \dfrac{1}{2} )+2<4M_N+2< m \leq 2n+1$となり矛盾。
$ \left|f_N(A'_k)-A'_k\right| \leq 2\quad B'_k,C'_k$についても同様。
$ A'_k< M_N$ならば$ A'_k=f_N(A'_k)$であるから明らかに成り立つ。$ A'_k \geq M_N$のとき$ k=i_t$とすると$ A'_k$は$ P_N$の$ t$番目の数である。$ f_N(A'_k)$は$ P'_N$の$ t$番目であるから$ P_N$の$ t+m$番目である。明らかに$ f_N(A'_k) \geq A'_k$であるから
$ f_N(A'_k)=p+q,A'_k=p$とし、$ q \geq 3$と仮定する。$ P_N$において$ A'_N$と$ f_N(A'_N)$の間に必ず$ p+1$が$ 2(p+1)$個、$p+2$が$ 2(p+2)$個存在するので$2(p+1)+2(p+2) \leq m$であるが
$ \dfrac{8}{3}n + 4 <4 ( \dfrac{2}{3} \sqrt{N}- \dfrac{1}{2} )+6<4M_N+6 \leq 4p+6< m \leq 2n+1$となり矛盾。よって補題を得る。
$ (A_k,B_k,C_k)=(f_N(A'_k),f_N(B'_k),f_N(C'_k))\,\quad k=1, \cdots ,n(n+1)$$\lbrace A_k,B_k,C_k \rbrace \in \lbrace M_N,M_N+1 \rbrace \quad k=n(n+1)+1, \cdots n(n+1)+m$
とすることで条件を満たすことを示す。ただし、$ M_N$か$ M_N+1$かについては$ (A_1, \cdots A_N),(B_1, \cdots B_N),(C_1, \cdots C_N)$が良い並び替えとなるように決める。
・$k=1, \cdots ,n(n+1)$のとき
$\left|A_k+B_k+C_k-2\sqrt{N}\right|$$=\left|f_N(A'_k)+f_N(B'_k)+f_N(C'_k)-2\sqrt{N}\right|$$ \leq \left|A'_k+B'_k+C'_k-2\sqrt{N}\right|+6$$=\left|2n+1-2\sqrt{n(n+1)+m}\right|+6$$=\dfrac{\left|4m-1\right|}{2n+1+2\sqrt{n(n+1)+m} }+6$$ \leq \dfrac{8n+3}{4n}+6 $$ \leq 3+6$$ \leq 9<2023-\dfrac{3}{2}$となり満たしている。
・$ k=n(n+1)+1, \cdots n(n+1)+m$のとき$ \left| \dfrac{2}{3} \sqrt{N}-M_N \right|< \dfrac{1}{2} $かつ$ \left| \dfrac{2}{3} \sqrt{N}-M_N-1 \right|< \dfrac{3}{2} $であるから
$\left|A_k+B_k+C_k-2\sqrt{N}\right|$$ \leq \left|\dfrac{2}{3} \sqrt{N}+\dfrac{2}{3} \sqrt{N}+\dfrac{2}{3} \sqrt{N}-2\sqrt{N}\right|+ \dfrac{9}{2} $$=\dfrac{9}{2}<2023 -\dfrac{3}{2}$となり満たしている。よって証明は完了した。
最後に
証明するために色々定義したら複雑になってしまった…。問題の$2023$という数字の部分をどこまで小さくできるのか気になる。
この記事を高評価した人
この記事に送られたバッジ
投稿者
