[E] modじゃんけん

hinu 自動ジャッジ 難易度: 数学 > 高校数学
2020年8月15日18:00 正解数: 8 / 解答数: 14 (正答率: 57.1%) ギブアップ不可
この問題はコンテスト「KOH Mathematical Contest #2」の問題です。

正答

5 9 1 3 7 2 7
6 4 2 5 3 1 0

解説

$n$ を自然数とする。$k\equiv r\;({\rm mod}\; 3)$ となる $0\leq k\leq n$ に対する和を $\displaystyle{\sum_{k\equiv r}}$ と表すことにする。まず,
$$
f_n(r)=\sum_{k\equiv r} {}_n{\rm C}_k
$$の表式を求めておく。二項定理より
$$
(1+x)^n={}_n{\rm C}_0+{}_n{\rm C}_1x+{}_n{\rm C}_2x^2+{}_n{\rm C}_3x^3+\cdots+{}_n{\rm C}_nx^n
$$が成り立つ。$1$ の虚立方根を $\omega$ とすると $\omega^3=1, \omega^2+\omega+1=0$ である。上式に $x=1,\omega, \omega^2$ を代入すると
\begin{align}
2^n&={}_n{\rm C}_0+{}_n{\rm C}_1+{}_n{\rm C}_2+{}_n{\rm C}_3+\cdots+{}_n{\rm C}_n\\
(-\omega^2)^n&={}_n{\rm C}_0+{}_n{\rm C}_1\omega+{}_n{\rm C}_2\omega^2+{}_n{\rm C}_3\omega^3+\cdots+{}_n{\rm C}_n\omega^n\\
(-\omega)^n&={}_n{\rm C}_0+{}_n{\rm C}_1\omega^2+{}_n{\rm C}_2\omega^4+{}_n{\rm C}_3\omega^6+\cdots+{}_n{\rm C}_n\omega^{2n}
\end{align}各辺を加えると
$$
3\sum_{k\equiv 0} {}_n{\rm C}_k=2^n+(-1)^n(\omega^n+\omega^{2n})=\begin{cases}
2^n+2\cdot (-1)^n & (n\equiv 0)\\
2^n-(-1)^n & (n\equiv 1,2)
\end{cases}
$$また,第 $1$ 式 $+$ 第 $2$ 式 $\times \; \omega\;+$ 第 $3$ 式 $\times \; \omega^2$ をつくると
$$
3\sum_{k\equiv 2} {}_n{\rm C}_k=2^n+(-1)^n(\omega^{n+2}+\omega^{2n+1})=\begin{cases}
2^n+2\cdot (-1)^n & (n\equiv 1)\\
2^n-(-1)^n & (n\equiv 0,2)
\end{cases}
$$同様に,第 $1$ 式 $+$ 第 $2$ 式 $\times \; \omega^2\;+$ 第 $3$ 式 $\times \; \omega$ をつくると
$$
3\sum_{k\equiv 1} {}_n{\rm C}_k=2^n+(-1)^n(\omega^{n+1}+\omega^{2n+2})=\begin{cases}
2^n+2\cdot (-1)^n & (n\equiv 2)\\
2^n-(-1)^n & (n\equiv 0,1)
\end{cases}
$$が得られる。したがって
$$
3f_n(r)=\begin{cases}
2^n+2\cdot (-1)^n & (n\equiv 3-r)\\
2^n-(-1)^n & ({\rm otherwise})
\end{cases}
$$が成り立つ。

この準備のもとで,あいこになる確率を求めていく。
$$
A=\sum_{j=1}^n a_j
$$とおく。

[1] $3$ 種類の数が選ばれるとき
$A$ を $3$ で割った余りは $0,1,2$ のいずれかだから,$a_1,\cdots, a_n$ の中に $0,1,2$ がすべて登場するとき,人 $1, \cdots, n$ のうち少なくとも $1$ 人は生存し $1$ 人は脱落する。よってこのときあいこになることはない。

[2] $1$ 種類の数のみが選ばれるとき
$a_1=\cdots=a_n$ ならば全員が生存するか脱落する。よってこのときには必ずあいこになる。これに該当する場合は $3$ 通り。

[3] $2$ 種類の数のみが選ばれるとき
(i) $0,1$ のみが選ばれるとき
$k=1,\cdots, n-1$ に対し,$a_1,\cdots, a_n$ のうち $n-k$ 個が $0$,$k$ 個が $1$ であるとする。このとき,あいこになるような $k$ が何通りあるかを求めればよい。$A=k$ だから,あいこになる条件は
$$
k\equiv 2\;({\rm mod}\; 3)
$$である。よって,あいこになる場合の数は,$f_n(2)-\delta_{n,2}$ である($\delta_{i,j}$ は $i\equiv j\pmod{3}$ のとき $1$,$i\not\equiv j$ のとき $0$ となる関数。$n\equiv 2$ のときには和から $k=n$ の項を除かなければならない)。

(ii) $0,2$ のみが選ばれるとき
$k=1,\cdots, n-1$ に対し,$a_1,\cdots, a_n$ のうち $n-k$ 個が $0$,$k$ 個が $2$ であるとする。$A=2k$ だから,あいこになる条件は
$$
2k\equiv 1\;({\rm mod}\; 3)
$$すなわち
$$
k\equiv 2\;({\rm mod}\; 3)
$$である。よって,あいこになる場合の数は (ii) と同じく $f_n(2)-\delta_{n,2}$ である。

(iii) $1,2$ のみが選ばれるとき
$k=1,\cdots, n-1$ に対し,$a_1,\cdots, a_n$ のうち $n-k$ 個が $1$,$k$ 個が $2$ であるとする。$A=n+k$ だから,あいこになる条件は
$$
n+k\equiv 0\;({\rm mod}\; 3)
$$である。よって,
$$
k\equiv \begin{cases}
0 & (n\equiv 0)\\
2 & (n\equiv 1)\\
1 & (n\equiv 2)
\end{cases}
$$が成り立つ。ゆえに,あいこになる場合の数は $f_n(3-n)-2\delta_{n,0}$ である($n\equiv 0$ のときには和から $k=0, n$ の項を除かなければならない)。

以上より,あいこになる場合の数は

(A) $n\equiv 0\; ({\rm mod}\; 3)$ のとき

$$
2f_n(2)+f_n(0)-2+3=\frac{2^{n+1}-2\cdot (-1)^n+2^n+2\cdot(-1)^n}{3}+1=2^n+1
$$

(B) $n\equiv 1\; ({\rm mod}\; 3)$ のとき

$$
3f_n(2)=2^n+2\cdot (-1)^n+3
$$

(C) $n\equiv 2\; ({\rm mod}\; 3)$ のとき

$$
2f_n(2)+f_n(1)-2+3=\frac{2^{n+1}-2\cdot (-1)^n+2^n+2\cdot(-1)^n}{3}+1=2^n+1
$$となる。以上をまとめると,あいこになる確率 $p_n$ は

$$
p_n=\begin{cases}
\cfrac{2^n+5}{3^n} & (n\equiv 4\; {\rm mod}\; 6)\\
\cfrac{2^n+1}{3^n} & ({\rm otherwise})
\end{cases}
$$となる。したがって

$$
p_2=\frac{5}{9},\;p_3=\frac{1}{3},\; p_4=\frac{7}{27},\;\lim_{n\to\infty} p_n=0
$$

である。


おすすめ問題

この問題を解いた人はこんな問題も解いています

[C] 奇妙な数列

ofukufukufuku 自動ジャッジ 難易度:
3年前

12

問題文

以下のような数列 $\{a_n\}$ を考える。
$$
a_n=1+\sum_{m=1}^{2^n}{\rm floor}\left[\sqrt[n]{\frac{n}{\displaystyle{\sum_{k=1}^m}\; {\rm floor}\left(\cos^2\cfrac{(k-1)!+1}{k}\pi\right)}}\right]
$$なお、${\rm floor}(x)$ は $x$ 以下の最大の整数を返す関数とする。このとき、$a_{20}$ を求めよ。

ただし、必要であれば以下の定理および不等式を用いても良い。

  1. $n$ が素数のとき
    $$\quad(n-1)!\equiv-1 \pmod n$$
  2. $n\geq 1$ のとき
    $$1\leq\sqrt[n]{n}<2$$

解答形式

半角数字で入力してください.

[A] よくある級数

ofukufukufuku 自動ジャッジ 難易度:
3年前

12

問題文

$y=\tan x \; \left(-\cfrac{\pi}{2}<x<\cfrac{\pi}{2}\right)$ の逆関数を $x=f(y)$ とする.このとき,
$$
S=\sum_{n=0}^\infty f\left(\frac{1}{n^2+n+1}\right)
$$を求めよ.答えは,整数ア・イを用いて
$$
S=\frac{\fbox{ア}}{\fbox{イ}}\pi
$$と既約分数の形でかける.

解答形式

アとイをそれぞれ1行目、2行目に半角数字で入力せよ.

[B] Dots on the Ball

halphy 自動ジャッジ 難易度:
3年前

25

問題文

$r$ を正の整数とする。$xyz$ 空間において,原点を中心とする半径 $\sqrt{r}$ の球面を $S_r$ で表すとき,次の問いに答えなさい。

  1. $S_r$ が格子点を含まないような最小の $r$ を求めなさい。
  2. $S_r$ が格子点を含まず,$r$ が $8$ の倍数であるような最小の $r$ を求めなさい。

※点 $(x,y,z)$ が格子点であるとは,$x,y,z$ がすべて整数であることをいう。

解答形式

改行区切りで,1行目に 1. の答えを,2行目に 2. の答えを入力してください。

Sandwich

halphy 自動ジャッジ 難易度:
4年前

11

問題文

ピザが1枚ずつ乗った $N\;(\geq 2)$ 枚の皿が横一列に並んでいます.ピザにはがあり,表には具がのっていて,裏にはのっていません.はじめ,すべての皿のピザは表が上になっています.これらのピザに対して,次の操作Xを考えます.

操作X:

  1. 隣り合う2枚の皿に着目し,左側の皿に乗っているピザをひっくり返し,右側の皿の一番上に重ねる.ピザが複数枚乗っている場合は,ピザを重ねたまままるごとひっくり返す.
  2. 左側の皿を取り除き,皿どうしのすき間を詰める.

この操作Xを$\;N-1\;$回繰り返すと,1枚の皿にピザの塔ができます.操作Xの $N-1$ 回の繰り返しをピザの調理ということにします.ピザの塔を構成するピザを,上から順に$\;P_i\; (i=1,\cdots, N)\;$とし,$P_i$ が表を上に向けているとき「表」,裏を上に向けているとき「裏」と書くことにすると,ピザの塔は「裏裏裏表」のように表すことができます.

$N=6$とします.「裏裏裏裏表表」というピザの塔ができるような調理は何通りあるか答えなさい.

解答形式

半角数字で入力してください.

[B]ネットワークの情報伝達

kaicho 自動ジャッジ 難易度:
3年前

11

問題文

次のようなネットワークを考える.
・情報として「0」または「1」の状態を各ノードは保持することができる.
・各ノードは他のノードに対して一方的に情報を伝達する.
・情報の伝達の際には,ある確率pで正しく状態を伝達するが,1-pの確率で状態が反転して伝達される.ここで,このpは枝によって値が異なることに注意する.
・2つのノードから情報が伝達される場合には,両方の情報を受け取った上で,保持する状態を決定する.このとき,2本のノードから受け取った情報が一致する場合には一致した状態を保持し,異なる情報を受け取った場合には1/2の確率で「0」を保持することにする(1/2の確率で「1」を保持することにする).
以下の図のネットワークにおいて始点の情報を終点まで伝達することを考え,始点と終点の状態が一致する確率xを求める.
ただし,矢印(枝)はノード間の情報伝達の方向を表し,枝の上に書かれている文字は正しく伝達される確率(上の説明のp)を表すものとする.

① a=2/3,b=3/4の場合のxを計算せよ.
② a=11/111,b=1/2の場合のxを計算せよ.
③ a=2/3,b=3/4の場合を考える.このネットワークはxy平面上の$3\times3$のサイズの格子点において,x軸正方向とy軸正方向に正しく情報が伝達される確率をそれぞれa,b,始点を原点,終点を点(2,2)としたものとみなせる.このとき,$n\times n$のサイズに拡張された(終点を(n,n)とする)ネットワークを考えると,$n\to \infty$とした時に,始点と終点の状態が一致する確率の収束値を求めよ.

解答形式

「分子/分母」(半角英数字)として既約分数を表せ.例)11/92
1行目に①,2行目に②,3行目に③を解答すること.

求面積問題6

Kinmokusei 自動ジャッジ 難易度:
3年前

9

問題文

図中、同じ印のついている辺・角同士は等しいです。
緑の凹四角形の面積が10のとき、青の三角形の面積を求めてください。

解答形式

半角数字で解答してください。

求角問題4

Kinmokusei 自動ジャッジ 難易度:
3年前

7

問題文

正六角形2つが図のように配置されています。赤い線分と青い線分の長さの比が1:4であるとき、緑で示した角Yの角度を求めてください。
ただし、図中"center"で示した点は正六角形の外心です。

解答形式

0~360までの半角数字で、「°」や「度」をつけずに解答してください。

求面積問題5

Kinmokusei 自動ジャッジ 難易度:
3年前

8

問題文

正方形が2つ、図のように配置されています。赤い線分の長さが20のとき、緑で示した四角形の面積を求めてください。
ただし、図中の青点はそれぞれの正方形の対角線の交点です。

解答形式

半角数字で解答してください。

[D] Eigensequence

halphy 自動ジャッジ 難易度:
3年前

6

問題文

漸化式
$$
a_{n+3}=3a_{n+2}-4a_{n+1}+2a_n\quad (n=1,2,\cdots)
$$および
$$
a_1=1, \; a_2=0, \; a_3=0
$$を満たす数列 $\{a_n\}$ を考える。次の空欄 $\fbox{ア}$ 〜 $\fbox{フ}$ に当てはまる数字を答えなさい。

  • 漸化式
    $$
    a_{n+3}=3a_{n+2}-4a_{n+1}+2a_n\quad (n=1,2,\cdots)
    $$を満たす数列全体の集合を $V$ とする。数列 $a_n, b_n\in V$ および $c\in\mathbb{C}$ に対して,第 $n$ 項が $ca_n, a_n+b_n$ であるような数列をそれぞれ数列 $a_n$ の $c$ 倍,数列 $a_n, b_n$ の和と定義することにすると,この和とスカラー倍により $V$ は $\mathbb{C}$ 上のベクトル空間になる(確かめよ)。ここで,$V$ の元 $a_n$ は,$a_1, a_2, a_3$ を定めることで完全に決定できる。すなわち,写像 $\varphi: V \to \mathbb{C}^3$ を
    $$
    \varphi(a_n)=\begin{pmatrix} a_1 \\ a_2 \\ a_3\end{pmatrix}
    $$で定めると,$\varphi$ は全単射である。しかも,$\varphi$ は線型写像だから,$\varphi$ はベクトル空間の同型になる。$V$ は $\fbox{ア}$ 次元である。また,$e_n^{(1)}, e_n^{(2)}, e_n^{(3)}\in V$ を
    $$
    \varphi(e_n^{(1)})=\begin{pmatrix} 1 \\ 0 \\ 0\end{pmatrix},\; \varphi(e_n^{(2)})=\begin{pmatrix} 0 \\ 1 \\ 0\end{pmatrix},\; \varphi(e_n^{(3)})=\begin{pmatrix} 0 \\ 0 \\ 1\end{pmatrix}
    $$となるように定めると,$e_n^{(1)}, e_n^{(2)}, e_n^{(3)}$ は $V$ の基底になる。

  • $V$ 上の線型変換 $L: V\to V$ を次のように定義する。$a_n\in V$ に対して,$L(a_n)$ を第 $1, 2, 3$ 項がそれぞれ $a_2, a_3, a_4$ である数列とする($L$ が線型写像になることを確かめよ)。このとき,$L(a_n)$ の第 $n$ 項は $a_{n+\fbox{イ}}$ である。基底 $e_n^{(1)}, e_n^{(2)}, e_n^{(3)}$ のもとでの $L$ の表現行列 $L_A$ は
    $$
    L_A=\begin{pmatrix} \fbox{ウ} & \fbox{エ} & * \\ \fbox{オ} & \fbox{カ} & \fbox{キ} \\ \fbox{ク} & \fbox{ケコ} & \fbox{サ}\end{pmatrix}
    $$である。

  • $L_A$ の固有値を $\lambda^{(1)}, \lambda^{(2)}, \lambda^{(3)}$ とする($\lambda^{(1)}\in\mathbb{R}, {\rm Im}(\lambda^{(2)})>0, {\rm Im}(\lambda^{(3)})<0$)。このとき
    \begin{align}
    \lambda^{(1)}&=\fbox{シ}\\
    {\rm Re}(\lambda^{(2)})={\rm Re}(\lambda^{(3)})&=\fbox{ス}\\
    {\rm Im}(\lambda^{(2)})=-{\rm Im}(\lambda^{(3)})&=\fbox{セ}
    \end{align}である。

  • 固有値 $\lambda^{(1)}, \lambda^{(2)}, \lambda^{(3)}$ に対応する固有ベクトルをそれぞれ $\alpha^{(1)}, \alpha^{(2)}, \alpha^{(3)}$ とする。固有ベクトルには定数倍の不定性があるが,$\alpha^{(j)}\;(j=1,2,3)$ の第 $1$ 成分が固有値 $\lambda^{(j)}$ に一致するようにとると
    \begin{align}
    \alpha^{(1)}=\begin{pmatrix} \lambda^{(1)} \\ \fbox{ソ} \\ * \end{pmatrix},\; \alpha^{(2)}=\begin{pmatrix} \lambda^{(2)} \\ \fbox{タ}\;i \\ * \end{pmatrix},\; \alpha^{(3)}=\begin{pmatrix} \lambda^{(3)} \\ * \\ \fbox{チツ}-\fbox{テ}\;i \end{pmatrix}
    \end{align}である。

  • $\varphi(\beta_n^{(1)})=\alpha^{(1)}, \;\varphi(\beta_n^{(2)})=\alpha^{(2)}, \;\varphi(\beta_n^{(3)})=\alpha^{(3)}$ となる数列 $\beta_n^{(1)}, \beta_n^{(2)}, \beta_n^{(3)}\in V$ をとる。$\beta_n^{(1)}, \beta_n^{(2)}, \beta_n^{(3)}\in V$ は $V$ の基底をなすから,$V$ の任意の元 $a_n$ はこれらの線型結合で表すことができる。例えば,$a_n\in V$ が
    $$
    a_1=1, \; a_2=0, \; a_3=0
    $$を満たすとき
    $$
    a_n=\fbox{ト}\;\beta_n^{(1)}-\frac{\beta_n^{(2)}-\beta_n^{(3)}}{\fbox{ナ}\; i}
    $$が成り立つ。これを変形すると
    $$
    a_n=\fbox{ニ}-\left(\sqrt{\fbox{ヌ}}\;\right)^n\sin\left(\frac{n\pi}{\fbox{ネ}}\right)
    $$となる。また,$a_1,\cdots, a_{100}$ のうち $a_n$ が最大となるのは $n=\fbox{ノハ}, \fbox{ヒフ}$ のときである。ただし $\fbox{ノハ} < \fbox{ヒフ}$ とする。

※この問題では,数列とは写像 $a: \mathbb{N} \to \mathbb{C}$ のことをいう。$n\in\mathbb{N}$ に対して,$a(n)$ のことを単に $a_n$ と表記する。また,記号の濫用であるが $a$ を $\{a_n\}, a_n$とも書く。

解答形式

空欄 $\fbox{ア}$ 〜 $\fbox{フ}$ には,半角数字 0 - 9 または記号 - のいずれかが当てはまります。$\fbox{ア}$ 〜 $\fbox{フ}$ に当てはまるものを改行区切りで入力してください。

問題

Kinmokusei 自動ジャッジ 難易度:
3年前

6

問題文

(2020.9.26 11:57追記)
解答形式に不備があったため、訂正致しました。

図の青、緑、赤の線分の長さを$X,Y,Z$、斜線部の面積を$S$とすると、次の式が成り立つ。
$$
\frac{[ア]}{S}=\frac{[イ]}{Z}\left(\frac{1}{X}+\frac{1}{Y}\right)
$$

なお、図の曲線は半円の弧である。

解答形式

$[ア],[イ]$にはともに自然数が入ります。その和を半角数字で解答してください。
ただし、その和が最小となるように解答してください。
例:$[ア]=4,[イ]=2$なら$6$ではなく(両辺を$2$で割ることにより)$3$と解答。

Factorial Fraction

sapphire15 自動ジャッジ 難易度:
4年前

22

問題文

非負整数$n$に対し関数$f$を次のように定める。

$$f(n) = \frac{(n^2)!}{(n!)^{n+1}}$$

$1$から$2020$までの整数について$f(n)$が整数となるような$n$の個数を求めよ。

解答形式

半角数字で入力せよ。

求面積問題8

Kinmokusei 自動ジャッジ 難易度:
3年前

13

問題文

△ABCと点Pをとり、△ABP, △BCP, △CAPの重心をそれぞれ$G_1, G_2, G_3$とします。青で示した3つの三角形の面積の和が10のとき、$△G_1G_2G_3$(赤い三角形)の面積を求めてください。

解答形式

半角数字で解答してください。