2024-02-11

数学オリンピック本選2024 第2問

任意の $m$ をとり, $f(m)\lt p$ かつ $\gcd(f(m),p)=1$ であるような素数 $p$ をとって, $n=p-f(m)$ とおく.

このとき $m|\text{lcm}(m,f(m+f(n)))=\text{lcm}(f(m),f(m)+n)=\text{lcm}(f(m),p)|f(m)p$ .

よって任意の $m$ に対して $m|f(m)$ が得られる.

次に $m=1$ , $n=f(1)$ とすると,

$f(1+f(1))=\text{lcm}(m,f(m+f(n)))=\text{lcm}(f(m),f(m)+n)=\text{lcm}(f(1),2f(1))=2f(1)$ .

前の議論から,ある自然数 $a$ により $f(1+f(1))=a(1+f(1))$ とおけるが, $a\geq 2$ と仮定すると, $2+2f(1)\leq a(1+f(1))=2f(1)$ より矛盾.

したがって $a=1$ であり, $1+f(1)=f(1+f(1))=2f(1)$ から $f(1)=1$ .

次に $m=1$ とすると,

$f(1+f(n))=\text{lcm}(m,f(m+f(n)))=\text{lcm}(f(m),f(m)+n)=\text{lcm}(1,1+n)=1+n$ .

前の議論から, $f(n)=an$ , $f(1+f(n))=b(1+f(n))$ とおくと $b+abn=1+n$ が得られ,結局 $a=b=1$ が必要.特に $f(n)=n$ が得られる.

逆に $f$ を $f(n)=n$ とすれば,両辺は $\text{lcm}(m,m+n)$ と等しいことが分かるので条件を満たす.

したがって求める関数は $f(n)=n$ のみである.

感想

あんまり見ないタイプの関数方程式だなあと思った.

2024-02-11

数学オリンピック本選2024 第1問

以下 $a_0$ は $a_{n}$ を, $a_{n+1}$ は $a_1$ を指すものとする.

$\{a_i\}$ の中で絶対値が最大なものの1つを $a_k$ と置く.

・ $a_k$ が正の場合.

$a_{k-1}\lt a_{k}$ だとすると

$|a_{k-1}-2a_{k}|=2a_{k}-a_{k-1}=a_k+(a_{k}-a_{k-1})\gt a_k=|a_k|$ であり矛盾.

よって $a_{k-1}= a_{k}$ .

これを繰り返すことで $\{a_i\}$ は全て等しいことが分かる.

・ $a_k$ が負の場合.

$a_{k-1}\gt a_{k}$ だとすると

$|a_{k-1}-2a_{k}|=a_{k-1}-2a_{k}=(a_{k-1}-a_k)-a_k\gt -a_k=|a_k|$ であり矛盾.

よって $a_{k-1}= a_{k}$ .

これを繰り返すことで $\{a_i\}$ は全て等しいことが分かる.

・ $a_k$ が0の場合.

$\{a_i\}$ は全て0なので全て等しい.

したがっていずれの場合も $\{a_i\}$ は全て等しいことが分かった.

これを $a$ とおくと条件から $a-2a=a$ が必要であり,つまり $a=0$ である.

ゆえに条件を満たすのは $\{a_i\}$ が全て $0$ の場合のみである.

感想

和が0になることぐらいはすぐに分かるしどうせ全部0の場合しかなさそうと思えるがその後の発想が少し難しい.思いつけば記述は簡単そう.

2023-08-10

競プロerが応用情報を受けた所感

ちょっと書いて面倒で放置してたら公開がこんな時期に…

伝えたいこと

・競プロerで受ける人はnok0さんのブログを参考にしましょう。

tsuchi.hateblo.jp

・午前は4割ぐらいは応用情報の過去問から出ます。それに加えて基本情報の過去問とかからも多少出るので過去問道場で過去問を回しまくるだけでいいです。

・午後は競プロerなら緑レート以上あれば大して対策しなくても通りそうな気がしました。

以下蛇足

スペック

・数学系の修士1年

・AtCoder黄

・学部の講義は文字通り片っ端から受けたので情報系の講義もそれなりにとっていた

受験まで

過去問を解いたら6割とれたので受けようかな～という気分になりました。

暇つぶしに応用情報技術者の過去問50問といたらちょうど6割とれたから春にでも受けようかな
ちょっと勉強すれば受かりそう pic.twitter.com/DOY5PpjXiK
— ねしゃ～ (@yuui_nesya) 2022年9月29日

基礎理論が全部とれてるのは学部の講義で習った内容とある程度被っているというのもあったと思います。

試験1か月前ぐらいまで何もやっていなくて流石に何かやった方がいいかな～と思っていたら、TOEICで500点だか600点だかとらないと卒業できなくてヤバい！って言っている友人が一緒に集まって勉強しようと言ってきたので勉強することにしました。

参考書についてですが、受験料で7500円も払ってるのにさらに金を払うのも馬鹿らしかったのでなんかいい方法ないかな～と思ったんですが、Maruzen eBook Libraryの大学で契約している本の中に応用情報の参考書があったのでそれを無料で読みました。「徹底攻略応用情報技術者教科書」ってやつです。

勉強方法としては、参考書を読み進めつつそれに対応する過去問を分野指定で解くのを繰り返しました。テクノロジ系は参考書を読んでいて多少は意味があったような気がしましたがマネジメント系とストラテジ系はあんまり意味がなかった気がします。参考書もそこの部分は適当に読み飛ばしました。

午後は前日まで対策しておらず、前日にnok0さんのブログとか同じ回を受ける友人の意見を参考にし、プログラミングと組込みシステム開発とシステム監査をとることにしてもう一つは会場で簡単そうなものを選ぶことにしました。

試験の感触

午前

思ったより過去問から丸々でているものが多いなと思いました。(実際かなりの割合が過去問の流用らしい。)

過去問を解いていた感じだと8割は確実にとれると思っていたのですが、今回のは難易度が高く解いていて7割ぐらいかな～となりました。

ドップラー効果の利用法みたいな問題もあってこんなの出るんだと思いました。

午後

情報セキュリティ…英語の略称を答える問題が2問ありしらね～～となり両方とも完全に勘になったし両方間違えた。

プログラミング…10分ぐらいで片づくと思ったが意外に手間取り30分ぐらいかかったがさすがに全完。

組込みシステム開発…問題文に書いてある仕様をちゃんと読めますかというだけで簡単だった。

システム監査…ただの国語でだいぶ簡単に思えたが、設問が嘘かと思うぐらい少なく1問間違えただけでだいぶ点が飛びそうで怖かった。

このあとどれを選択するか迷ったが計算問題が見え他の問題も大体解けそうだったシステムアーキテクチャを選択

システムアーキテクチャ…データ形式を答える問題で唯一知っているCSVと答えたら間違えた。ほとんど読めば解ける問題だと思って選んだが最終問題が普通に知識がなく見当違いなことを書いて終了。

結果

午前:71.25点

午後:89.00点

でした。

応用情報技術者試験合格しました！ pic.twitter.com/on8YEewMj5
— ねしゃ～ (@yuui_nesya) 2023年6月29日

午後は

情報セキュリティ 16/20
プログラミング 20/20
システムアーキテクチャ 14/20
組み込みシステム開発 19/20
システム監査 20/20

ぐらいの感触です。

感想

ノー勉でいけるやろｗとか思ってたんですがこの難易度だと午前は勉強してなかったら落ちていた気がするので勉強しておいてよかったです。

午後は競プロをやってるならある程度問題文の読解もできるはずで、プログラミング・組み込みシステム開発・システム監査は高得点が取れるんじゃないかと思いました。もう1つは適当に選んでください。

解答例を出している会社が複数あり試験後に眺めていたんですが、システム監査の解答例が記号問題すらめちゃくちゃに割れていて面白かった。ただの国語の問題だと思ったけど思ったより難しいのかもしれない。

一緒に勉強していた友人はTOEICの点が全然足りなかったけど大学の救済用の試験を受けて無事単位が取れたらしいです。

2023-02-18

ねしゃ～

この記事の項目名には以下のような表記揺れがあります。

ねしゃ～

ねしゃー

ねしゃ

ネシャア

ネシャー

nesya

Nesya

nesya-

Nesya-

nesya~

Nesya~

nesyã

Nesyã

Nesyarote

Nesyarlathotep

涅紗亞

📝この項目「ねしゃ～」は、内容をより充実させるため、加筆が求められています。

2023-02-13

数学オリンピック本選2023 第4問

www.imojp.org

前提知識

$p=2$ 版のLTEの補題として以下が成り立つ(証明はLTEの補題とその応用～一般化へ向けて～ | Mathlogの定理3とかを参考にするといいです)

$n$ が偶数かつ $v_2(x)=v_2(y)=0$ のとき

$v_2(x^n-y^n)=v_2(x^2-y^2)+v_2(n)-1$

特に $y=1$ なら

$v_2(x^n-1)=v_2(x+1)+v_2(x-1)+v_2(n)-1\geq v_2(x-1)+v_2(n)$

LTEの補題を使わずに

$n=b\cdot 2^a (a=v_2(n))$ とおいて

$x^n-1=(x^{b\cdot 2^{a-1}}+1)(x^{b\cdot 2^{a-2}}+1)\cdots (x^{b}+1)(x-1)(x^{b-1}+x^{b-2}\cdots +1)$

を用いて直接求めてもよい

解法

$n=p_1^{e_1} \dots p_k^{e_k}$ ( $p_i$ は互いに異なる素数)とおくと

$d(n)=(e_1+1)\dots (e_k+1)$

$\phi (n)=p_1^{e_1-1} \dots p_k^{e_k-1} (p_1-1)\dots (p_k-1)$

よって $e_i\gt 1$ となるような $i$ があった場合 $\phi (n)$ が $p_i$ で割り切れるので $\phi (n)^{d(n)}+1$ が $p_i$ で割り切れず1つ目の条件に矛盾

したがって整理すると

$n=p_1 \dots p_k$

$d(n)=2^k$

$\phi (n)=(p_1-1)\dots (p_k-1)$

と表せる

$p_i$ に偶素数と奇素数がともに含まれていた場合 $\phi (n)^{d(n)}+1$ は奇数で $n$ は偶数になるので矛盾

偶素数のみの場合は $n=2$ しかありえずこれは条件を満たす

また $n=1$ は条件を満たさない

以下 $p_i$ は全て奇素数で $k\geq 1$ とする

1つ目の条件は $\phi(n)^{2^k}\equiv -1\pmod n$ と書け、中国剰余定理より任意の $i$ において、

$\phi(n)^{2^k}\equiv -1\pmod {p_i}$

$a$ を $p_i$ の原始根とし $a^m \equiv \phi(n)\pmod {p_i}(m\lt p_i-1)$ だとすると $a^{m\cdot 2^k}\equiv -1\pmod {p_i}$ だから

$(p_i-1)/2\mid m\cdot 2^k$ かつ $p_i-1\nmid m\cdot 2^k$ *1

したがって $v_2(p_i-1)=v_2(m\cdot 2^k)+1=v_2(m)+k+1\geq k+1\cdots (1)$

2つ目の条件に着目する

$\phi(n)$ が偶数かつ $n$ は奇数だから $p=2$ 版のLTEの補題を使うと

$v_2(n^{\phi(n)}-1)\geq v_2(n-1)+v_2(\phi(n))\cdots (2)$

$(1)$ より任意の $i$ において $p_i\equiv 1\pmod{2^{k+1}}$ なので、 $n\equiv 1\pmod{2^{k+1}}$ となり

$v_2(n-1)\geq k+1\cdots (3)$

また $\phi (n)=(p_1-1)\dots (p_k-1)$ 及び $(1)$ より

$v_2(\phi(n))\geq k(k+1)\cdots (4)$

よって $(2),(3),(4)$ より $v_2(n^{\phi(n)}-1)\geq (k+1)^2$

ここで $v_2(d(n)^5)=v_2(2^{5k})=5k$ だから

2つ目の条件より $(k+1)^2\lt 5k$

したがって $k=1,2$

・ $k=1$ の場合

$(\phi(n)^{d(n)}+1)/n=( (p_1-1)^2+1)/p_1=p_1-2+2/p_1$ より整数とならないので矛盾

・ $k=2$ の場合

$v_2(p_i-1)\geq k+1=3$ が成り立つ

ここで $v_2(p_1-1)=v_2(p_2-1)=3$ を仮定すると

$n=p_1 p_2$ だから $v_2(n-1)\geq 4$ より $(2),(4)$ と併せて

$v_2(n^{\phi(n)}-1)\geq 10=v_2(d(n)^5)$ より矛盾

一般性を失わずに $v_2(p_1-1)\geq 4$ とする

$v_2(\phi (n))=v_2( (p_1-1)(p_2-1))=v_2(p_1-1)+v_2(p_2-1)\geq 7$ だから $(2),(3)$ と併せて

$v_2(n^{\phi(n)}-1)\geq 10=v_2(d(n)^5)$ より矛盾

したがって条件を満たすのは $n=2$ のみである

*1: $(ℤ/p_iℤ)^×$ は位数 $p_i-1$ の巡回群であり、 $a^{(p_i-1)/2}\equiv -1$ になることを利用している

2023-02-12

数学オリンピック本選2023 第3問

www.imojp.org

$f$ を $f(x)=$ ( $a_i\leq x+c$ となる $i$ の個数)として定義するとこれは広義単調増加である

数列のすべての項が等しいとすると $a_{n+1}+c$ 以下の $a_i$ の個数は $0$ または無数にあるから明らかに矛盾

ある $k$ において $a_k\gt a_{k+1}$ だと仮定すると、 $f(a_{k+1})=a_k,f(a_{k+2})=a_{k+1}$ であり $f$ の広義単調増加性から $a_{k+1}\gt a_{k+2}$ となるので帰納的に $a_k$ 以降は狭義単調減少、よって $a_{k+a_k}\leq 0$ より矛盾

したがって数列は広義単調増加

また同様にしてある $k$ において $a_k\lt a_{k+1}$ だと仮定すると、 $a_{k+1}\lt a_{k+2}$ が示せるから、 $a_i\lt a_{i+1}$ を満たす最も小さい $i+1$ を $m$ とおくと、帰納的に $m$ 項目以降は狭義単調増加であり $a_m$ 以上の項は数列内で高々1個