TMC002の解説(前篇)

前書き

先日TMC002を開催したので,その解説を書きます.誤植がある可能性があるので見つけたら教えてくれると助かります.
コンテストページは こちら からどうぞ!

解説

A

青い部分の面積を求める
中学入試にありそうな問題ですね.(既出か？)ぜひ一度考えてみてください.

解説

直線$AB$と直線$CM$の交点を$R$とします.$\triangle ARM \equiv \triangle FCM$であるので$AR=2$です.$\triangle ARP \sim \triangle OCP$であるので$OP=\dfrac{1}{3}$です.$\triangle RBQ \sim \triangle COQ$であるので$OQ=\dfrac{1}{4}$です.$\angle AOB=60 \degree$なので,三角形$OPQ$の面積は$\dfrac{1}{2}\cdot OP\cdot OQ\cdot\sin 60\degree=\dfrac{1}{2} \cdot\dfrac{1}{3}\cdot\dfrac{1}{4}\cdot\dfrac{\sqrt{3}}{2}=\dfrac{\sqrt{3}}{48}=\dfrac{1}{\sqrt{768}}$.よって回答すべきは$\mathbf{768}$.

いくつかの線を書き足す
いかがでしたか？$3$つの相似が同時に出てくるのが素敵ですね!(をかし)

B

開催日がエイプリルフールであったことにちなんだ問題です.問題が嘘ってことはないので安心してください.ちなみに,TMCあるあるとしてBは難しくCは簡単です.

解説

ここでは母関数を用います.最上位の桁は$1,4,9$,その他の桁は$0,1,4,9$をとりうることに注意しましょう. $1,4 \equiv 1 \pmod3$で$,0,9 \equiv 0 \pmod3$ であるので$f(x) = (2x+1) \cdot (2x+2)^{998}$ を展開したときに出てくる項のうち,次数が$3$の倍数であるものの係数の総和を求めればよいです.$1$の$3$乗根のうち$1$でないものの一つ$\omega$をとってきます.$f(\omega)=(2\omega+1)(2\omega+2)^{998}=(2\omega+1)\cdot (-2\omega^2)^{998}=(2\omega+1)\cdot 2^{998}\cdot\omega=(2\omega^2+\omega)\cdot2^{998}$
$f(\omega^2)=(2\omega^2+1)(2\omega^2+2)^{998}=(2\omega^2+1)\cdot (-2\omega)^{998}=(2\omega^2+1)\cdot 2^{998}\cdot\omega^2=(2\omega+\omega^2)\cdot2^{998}$
$f(1)=3\cdot4^{998}$
よって項の係数の和は $N=\dfrac{f(1)+f(\omega)+f(\omega^2)}{3}=4^{998}-2^{998}$となります.次に,これの下三桁を求めます.以下,合同式の法を$125$とします.$4^{998}-2^{998}=2^{998}(2^{998}-1)$で,これは$8$の倍数です.また,$\dfrac{1}{4} \equiv 94$で,$\phi(125)=100 \mid 1000$であるから$N \equiv 94\cdot 93=8742\equiv117$です.$N=125k+117$とおいて,これが$8$の倍数であるから$k\equiv 7 \pmod8$.よって$k=8l+7$を代入することで,下三桁が$\mathbf{992}$とわかります.

典型的なroot of unity filterの問題です.下三桁を求めるパートが重くなってしまったのが良くないですね.Gの方こそいみじうをかしけれ.

C

解説

$\left\lfloor\ 9.9n \right\rfloor$が$10$の倍数であればよいです.$n$を$10$で割った商,あまりをそれぞれ$q,r$とします.つまり$n=10q+r$とおきます.$\left\lfloor\ \dfrac{99n}{10} \right\rfloor=\left\lfloor\ \dfrac{990q+99r}{10} \right\rfloor=\left\lfloor\ 99q+\dfrac{99r}{10} \right\rfloor=99q+\left\lfloor\dfrac{99r}{10} \right\rfloor\cdots$①です.
(1)$r=0$の時
①$=99q$となるのでこれが$10$の倍数となるためには$q$が$10$の倍数である必要がありこの時$n$の最小値は$100$です.
(2)$r=1,2,\cdots 9$のとき
$\left\lfloor\dfrac{99r}{10} \right\rfloor=\left\lfloor 10r-\dfrac{r}{10} \right\rfloor =10r+\left\lfloor-\dfrac{r}{10} \right\rfloor =10r-1\equiv 9 \pmod{10}$
よって,$q\equiv9 \pmod{10}$です.この時$n$の最小値は$91$となります.
(1),(2)より,$n$の最小値は$\mathbf{91}$となります.

Bより簡単ですね.個人的には結構好きです.

D

やや込み入った設定に見えますが,少し考えれば単純な問題に帰着します.

解説

$108=2^2\cdot3^3$です.これより$S$の要素は$2^a\cdot3^b$と表せます.ただし$a=0,1,2$,$b=0,1,2,3$です.ここで$3$行$4$列のマス目を黒く塗りつぶすことを考え,$2^a\cdot3^b$を$a+1$行$b+1$列目のマスに対応させます.この時,$f_{2,i}(U)$は$i+1$行目にある黒いマスの個数,$f_{3,j}(U)$は$j+1$列目にある黒いマスの個数に対応します.すると問題の条件は
「どの列にある黒いマスの個数も相異なるかつ,どの行にある黒いマスの個数も相異なる」
と言い換えられます.どの列にある黒いマスの個数も相異なりますが,ある列にある黒いマスの個数としてありうるものは$0,1,2,3$の$4$通りであるため順序を除いて各列にある黒いマスの個数は$0,1,2,3$個となります.これより黒いマスの総数は$6$個です.$3$個(すべて)塗られている列が存在するためどの行も少なくとも$1$マス塗られています.よって各行にある黒いマスの個数は順序を除いて$1,2,3$個です.ここで各行に着目し,まず$3$個塗る行を塗ります($12$通り).すると一つも塗られない列が存在するのだから次に$2$個塗る行を塗る塗り方は$6$通りです.最後に$1$個塗る行を塗る塗り方は$2$通りです.以上より求める部分集合の個数は$$12\cdot6\cdot2=\mathbf{144}$$個です.

見た目よりは難しいです.これも既出っぽいですね.

解説

abc
def
ghi
と各マスの数字を置きます.$4$つの$2\times2$のグリッドについて,そこに書かれている数字の和を全て足すと$S=a+c+g+i+2(b+d+f+h)+4e=45+b+d+f+h+3e\ge62$となり実際に$j=16$を満たす配置は存在するので,$j_{min}=16$です.ではそのような配置が幾つ存在するか数えます.$e\ge3$の時,$S\ge66$となり条件に反するため$e=1,2$です.ここで,例えば$b$に対して$h$を向かい合った位置,$d$や$f$を隣り合った位置といい,また$b$は$d,f$に挟まれた位置にあるといいます.
(1)$e=2$のとき
$(b,d,f,h)$は順序を除いて$(1,3,4,5)$と決まります.$5$に対して$4$が隣り合った位置にあるとき,$4,5$に挟まれた位置における数字は$5$以下となり不適です.よって$4,5$は互いに向かい合った位置にあります.すると$3,5$に挟まれた位置には$6$のみが入ります.次に$3,4$に挟まれた位置には$7$が入り,$1,5$に挟まれた位置に$8$が入り,$1,4$に挟まれた位置に$9$が入るので,$b,d,f,h$を決めれば$a,c,g,i$は一意に定まります.よって$4,5$の位置が$4$通り,$1,3$の位置が$2$通りあるので$8$通り.
(2)$e=1$のとき
$b+d+f+h \le 16$となり,残りの数字は$2,3,4,5,6,7,8,9$です.ここから$4$つを選んで和が$16$以下となる組み合わせは,$(2,3,4,5),(2,3,4,6),(2,3,4,7),(2,3,5,6)$の$4$パターン存在します.それぞれについて,残りの角のマス$a,c,g,i$に入る配置を数え上げます.各角のマスに入る数字は,$16$から$e=1$と隣り合う$2$つの十字マスの数字を引いた値以下になる必要があります.
(i) $(b,d,f,h)$が順序を除いて$(2,3,4,5)$のとき,残りの数字は$6,7,8,9$です.
$4,5$が向かい合った位置にあるとき,例えば$(b,h)=(4,5)$とすると,$(d,f)$は$(2,3)$か$(3,2)$です.それぞれにおいて,$a,c,g,i$に入る数字の許容される最大値が定まり,それに$6,7,8,9$を割り当てる方法は$4$通り存在します.$4,5$の位置の選び方が$4$通り,$2,3$の位置の選び方が$2$通りあるので,$4 \times 2 \times 4 = 32$通りです. 一方,$4,5$が隣り合った位置にあるとき,$4,5$に挟まれた位置の許容最大値は$15-(4+5)=6$となり,そこには$6$のみが入ります.十字の並びが円順列として$(4,5,2,3)$となる$8$通りの配置に対して,残りの角の入れ方が$2$通りあり$16$通りです.並びが$(4,5,3,2)$となる$8$通りの配置でも同様に$2$通りあり$16$通りです. よって,このパターンは合計して$64$通りとなります.
(ii) $(b,d,f,h)$が順序を除いて$(2,3,4,6)$のとき,残りの数字は$5,7,8,9$です.
$4,6$が向かい合った位置にあるとき,制約から角に入れる数字の組み合わせは一意に定まり,$8$通りとなります.
$4,6$が隣り合った位置にあるとき,$4,6$に挟まれた位置には許容最大値の制約から$5$のみが入ります.十字の並びが円順列として$(4,6,2,3)$となる$8$通りの配置では残りの角の入れ方が一意に決まり$8$通りですが,$(4,6,3,2)$となる配置では許容最大値の制約を満たすように残りの数字を入れることができません($0$通り). よって,このパターンは合計して$16$通りとなります.
(iii) $(b,d,f,h)$が順序を除いて$(2,3,4,7)$のとき,残りの数字は$5,6,8,9$です.
$S \ge 64$の不等式においてゆとりが無いため,全ての$2\times2$の枠の和がちょうど$16$になる必要があります.$4,7$が隣り合うと和が$16$を超えてしまうため,これらは向かい合った位置になければなりません.その配置に対して,和がちょうど$16$になるように角の数字を入れる方法は一意に定まります.よって$8$通りです.
(iv) $(b,d,f,h)$が順序を除いて$(2,3,5,6)$のとき,残りの数字は$4,7,8,9$です.
(iii)と同様に全ての$2\times2$の枠の和がちょうど$16$になる必要がありますが,十字マスをどのように配置しても,条件を満たすように残りの$4,7,8,9$を入れることはできません.よって$0$通りです.
以上より,$e=1$のときは$64 + 16 + 8 + 0 = 88$通り存在します.
(1)の$8$通りと合わせて,条件$j_{min}=16$を満たすような数字の書き込み方は$8 + 88 = \mathbf{96}$通りとなります.

はい.(2)の解説は億劫だったのでgeminiに書かせました.(気づいた？)東大とかで出そうですよね.

前篇終わり

前半戦終了です.個人的には簡単だけど解法がシンプルなA,Cが好きです.まあ後半からが戦いです.(特にHとかは記述したら大変)