0

自作問題紹介(+蛇足)

88
0
$$$$

SMC( https://jmosmc.crayonsite.com ) にて出題した自作問題の紹介と解説をしたいと思います。

 $100\times100$ のマス目があります. 左から $i$ 列目, 上から $j$ 行目のマスをマス $(j-1)\times100+i$ と呼ぶことにします. OMC 君は一般的な $6$ 面サイコロを $10000$ 回振り $k=1,2,\dots,10000$ について $k$ 回目に出た目をマス $k$ に書き込みます. このとき以下の条件を満たすような目の出方を $M$ とします.

  • $k=1,2,\dots,100$ について $k$ 行目に書かれた数字の総和は $2$ の倍数 .
  • $k=1,2,\dots,100$ について $k$ 列目に書かれた数字の総和は $3$ の倍数 .

 $M$ を求めてください.

解法$1$

 マスに整数を書き込む順番は無視しても一般性を失わないから, $k$$k$列目($k=1,2,\dots,100$)以外(すなわち左上から右下にかける対角線を除いた全マス)に既に数が書き込まれているとする. このとき, 以下が成立.

  • $k=1,2,\dots,100$ について $k$ 行目に書かれた数字の総和が $2$ の倍数となりかつ $k$ 列目に書かれた数字の総和が $3$ の倍数となるように $k$$k$ 列目に書き込まれるべき数は中国剰余定理より常に $1$ 通り .

したがって, $M=6^{100\times100-100}$ .

解法2(蛇足)
 $i$$j$ 列目に書き込まれた数を$a_{i,j}$ とする. このとき条件は以下が成立することである.

  • $P_i=a_{i,1}+a_{i,2}+\dots+a_{i,100}\equiv 0\pmod2\quad(i=1,2,\dots,100)$
  • $Q_i=a_{1,i}+a_{2,i}+\dots+a_{100,i}\equiv 0\pmod3\quad(i=1,2,\dots,100)$

ここで, $P_i$ に変数 $x_i$ を対応づけて, $Q_i$ に変数 $y_i$ を対応づけると, $M$ は以下の多項式を展開したとき, $x_i\quad(i=1,2,\dots,100)$ の次数が偶数かつ, $y_i\quad(i=1,2,\dots,100)$ の次数が $3$ の倍数である項の係数の総和である.
$$F=\prod_{i=1}^{100}\prod_{j=1}^{100}(x_iy_j+x_i^2y_j^2+x_i^3y_j^3+x_i^4y_j^4+x_i^5y_j^5+x_i^6y_j^6)$$
 
したがって, これは $F$$x_i\in\{1,-1\},y_i\in\{1,\omega,\omega^2\}\quad(i=1,2,\dots,100)$ を満たす$2^{100}3^{100}$ 通りの複素数の組 $(x_1,x_2,\dots,x_{100},y_1,y_2,\dots,y_{100})$ を代入した値の平均である. $x_iy_j\in\{-1,\omega,-\omega,\omega^2,-\omega^2\}$ なる $i,j$ が存在するとき, $F=0$ となるから$(x_1,\dots,x_{100},y_1,\dots,y_{100})=(1,1,\dots,1)$ を代入したときの $F=6^{100\times100}$$2^{100}3^{100}$ で割った値が $M=6^{9900}$ である.

余談:問題設定と同時に解法 $2$ を思いついたので、当初は難問が生えたと思ったのですが、よくよく考えたらそこまで高度なことをしなくても解けてしまいました()。

投稿日:223
更新日:429
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

MARTH
MARTH
6
1318
OMC黄

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中