OMC055 (4b) の話

初めまして、こんにちは！　よく OMC に参加している HighSpeed です。

今まで OMC の参加記事を書いていた locker 氏が、参加記事の投稿をやめてしまうということなので、その代わりとまではいきませんが、自分が記事を書いてみようと思いました。

ただ、次回以降書くかは未定です。需要もあるか分かりませんしね。

執筆にあたっては、locker 氏の記事をかなり参考にしました。というよりパクりました。ありがとう、そしてごめんね！

加えて初投稿で、またこのような記事を書くのも初めてですので、ご了承を。

さて、前置きはこれくらいにして、早速本題に移りましょう！

OMC055 (4b) には solver として参加しました。問題番号の横の数字は配点です。

A (100)

はい。これは秒殺できるタイプの 100 ですね。

$${123^n}$$ の $${1}$$ の位が、$${3 \to 9 \to 7 \to 1 \to\cdots}$$ のように $${4}$$ つ周期であることから求まります。

B (200)

求めるのは最小値なので、$${\mathbf P}$$ と$${\mathbf Q}$$の位置に注意です！！

上のような図が書ければ、かなり見通しは立てやすいのかな、と思います。$${\triangle\mathrm{AMP}}$$ に三平方の定理を用いることで、$${2}$$ 次方程式に帰着されます。

三平方の定理を用いたとき、$${3}$$ を $${2}$$ 乗し忘れそうになったのは秘密。

C (200)

$${10}$$ 進法では偽な命題 ($${1}$$ 以上 $${100}$$ 未満の整数の総和は $${4950}$$) でも、別の $${N}$$ 進法では真な命題になっている、という問題。

自分ははじめ、$${9900}$$ のみを $${N}$$ 進法で考える、というミスをし、$${N}$$ が整数にならず、後回しにしました……。E の後に戻ってきて、無事ミスに気が付きました。

はじめ $${N}$$ の $${4}$$ 次式になりますが、どんどん因数が外せて、最終的に $${N}$$ の $${1}$$ 次式になるのが爽快でした！

D (300)

$${2}$$ 個の節目で分けられた $${3}$$ つの部分の長さが、三角不等式を満たすようなものを数え上げる問題。工夫しないと数え上げるのが大変そうです。

実はこの問題、昔似たような問題を後輩に出されたことがありました！　そのとき教えてもらった解法を、この問題用にアレンジしたものを紹介します。自分はコンテスト中、これで解きました。

任意の合同な正三角形に対し、その内部のどこに点を打っても、$${3}$$ 辺に下した垂線の長さの合計が等しいことを利用します。

$${2021}$$ を一般に $${n}$$ として考え、$${3}$$ 辺に下した垂線の長さの合計が $${n}$$ になるように正三角形を定めます。

このとき、$${3}$$ 辺に下した垂線の長さを $${3}$$ 辺に持つ三角形が作れる（$${3}$$ 辺に下した垂線の長さが $${3}$$ つの三角不等式を全て満たす）のは、正三角形の各辺の中点を結んでできる、相似比 $${1/2}$$ の正三角形の内部です。

例えば $${n = 9}$$ の場合に、$${3}$$ 辺に下した垂線の長さが全て整数になる点、およびそれを $${3}$$ 辺に持つ三角形が作れる範囲を図示すると、以下のようになります。

したがって $${n = 2021}$$ のとき、求める値は $${1}$$ から $${1010}$$ までの整数の総和で、答えは $${\bm{510555}}$$ になります。

E (300)

FA でした！　やったね。

特別な大きさの角になっているので、三角比を利用したいと思いました。

$${\mathrm B,\, \mathrm P,\, \mathrm Q}$$ から $${\mathrm{AC}}$$ に下した垂線の足を $${\mathrm H,\, \mathrm I,\, \mathrm J}$$ とすると、

$$
\sqrt3 \, \mathrm{BH} = \left(2\sqrt3 + 1\right) \mathrm{PI} = \left(2\sqrt3 - 1\right) \mathrm{QJ} = \mathrm{AC}
$$

から $${\triangle\mathrm{APC} - \triangle\mathrm{AQC} = \triangle\mathrm{APQ}}$$ と $${\triangle\mathrm{ABC}}$$ の面積比が分かります。

ただし $${\tan 75^\circ = 2 + \sqrt3}$$ を用いてます。この公式は容易に示せますが、たまに使う場面があるので、覚えておいてもいいかもしれません。覚えるときは $${\tan 15^\circ = 2 - \sqrt3}$$ もセットで覚えてみてください。

公式解説のように、$${15^\circ,\, 75^\circ}$$ の三角比を使わなくても解けます。上の方針でも、$${\mathrm B,\, \mathrm P}$$ から $${\mathrm{AC}}$$ に下した垂線と $${\mathrm C,\, \mathrm Q}$$ から $${\mathrm{AB}}$$ に下した垂線にすれば、同様に解けます。

F (400)

問題設定を理解するのが難しいタイプですね。E を解いた後、C のミスを発見できる前に F を開いたのですが、さっと閉じて C に戻りました。

$${16 \times 16}$$ の実験で規則性に気が付き、頭の中で軽く証明し提出したものの、WA。

そしてすぐミスに気が付いたのですが、なんと $${\mathrm{popcount}(27) = 3}$$ ($${\mathrm{popcount}}$$ は $${2}$$ 進数表示での桁和）としていたのです……。ヤバすぎる、反省。

ところで公式解説では、一般に $${n = 2^{2021} - 2021}$$ としたときの $${M \coloneqq M(n)}$$ の値が $${3^{\mathrm{popcount}(n)}}$$ である、と突然出てきますが、これは以下のように理解することができます。

まず、操作を行う前のタイルの並びを考え、あるタイルの 2 × 2 から欠けているマスについて、タイルが置かれていない状態にするのに必要な操作の最小回数（「良い操作の回数」と呼ぶことにします）を k とすると、そのタイルが置かれている $${3}$$ マスについて、良い操作の回数はいずれも $${(k + 1)}$$ 回です。

このとき、$${2^m \times 2^m}$$ のマス目に対して、良い操作の回数が最も多いマスについて、その回数は $${(2^m - 1)}$$ 回であること、さらに上の $${M(n)}$$ について $${M(n) = 3^{\mathrm{popcount}(n)}}$$ が、以下のように $${m}$$ に関する帰納法で分かります。

$${m = 1}$$ では自明です。

また $${m}$$ で成立するとき、$${2^{m + 1} \times 2^{m + 1}}$$ のマス目を考えれば、最初に規則 1 を適用したときの、次回規則 2 を適用する領域 $${T_2}$$ に関して、次回規則 1 を適用する領域 $${T_1}$$ におけるマス目の良い操作の回数に $${2^m}$$ を加えたものを $${3}$$ つ合わせたようになっている (例えば $${m = 2}$$ では下図のようになる) ことが分かります。

なぜなら、$${2}$$ 回目の規則の適用のとき、$${T_2}$$ に対する規則 2 というのは、$${T_2}$$ を $${3}$$ つの $${2^m \times 2^m}$$ のマス目に分けて考え、$${T_1}$$ に対する規則 1 での $${(1, 1)}$$ を、それぞれ $${(2^m - 1, 2^m),\, (2^m, 2^m),\, (2^m, 2^m - 1)}$$ として適用したのと同じように考えられるからです。

$${T_1}$$ には帰納法の仮定が適用できるため、良い操作の回数が最も多いマスは $${(2^m - 1) + 2^m = 2^{m + 1} - 1}$$ です。$${M(n)}$$ についても、$${2}$$ 進法で $${m}$$ 桁以下の $${n}$$ について、$${2^m}$$ の位に $${1}$$ が付け加えられると $${M(n)}$$ が $${3}$$ 倍になることから、帰納法の仮定と合わせて、$${M(n) = 3^{\mathrm{popcount}(n)}}$$ はこのサイズのマス目に対しても成立します。よって、$${m + 1}$$ でも成立します。 

全体を通して

4b にしては少し難しめのセットであったような印象です。記事も長くなってしまいました。次回以降もし記事を書くなら、もう少しボリュームを落とそうかな、と思います。

自分は C と F のミスが少しもったいなかったです。凡ミスは減らしていかなければと思います。

次回は OMC056（無印）ですね！　4e だと勘違いしていたのをこれまた locker 氏が教えてくれました。感謝。

最後までお読みいただきありがとうございました！