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

kaicho 自動ジャッジ 難易度: 数学 > 高校数学
2020年9月12日18:00 正解数: 7 / 解答数: 11 (正答率: 63.6%) ギブアップ数: 0
この問題はコンテスト「Okapin Mathematical Contest」の問題です。

問題文

次のようなネットワークを考える.
・情報として「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行目に③を解答すること.


ヒント1

補題1 以下の二つのネットワークは等価であることを示せ.

ヒント2

補題2 以下の二つのネットワークは等価であることを示せ.


スポンサーリンク

解答提出

この問題は自動ジャッジの問題です。 解答形式が指定されていればそれにしたがって解答してください。

Sign in with Google Discordでログイン パスワードでログイン

ログインすると? ログインすると、解答・ギブアップをする他に、問題を投稿したり、ランキングで競うことができます。

または


おすすめ問題

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

求面積問題6

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

5

問題文

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

解答形式

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

[E] modじゃんけん

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

12

問題文

$n\;(\geq 2)$ を自然数とするとき,以下の試行を行うことを考える。


試行

  • $n$ 人が $0,1,2$ のいずれかひとつの数を無作為に選ぶ。
  • 人 $i\; (i=1,2,\cdots, n)$ が選んだ数を $a_i$ とする。各人 $i$ に対して,
    $$
    a_i\equiv\sum_{j=1}^n a_j\; ({\rm mod} \; 3)
    $$ならば人 $i$ は生存し,そうでないなら脱落する。この試行をmodじゃんけんと呼ぶことにする。

$n$ 人がmodじゃんけんを $1$ 回行い,全員が生存するか全員が脱落するとき,modじゃんけんの結果はあいこになると定義する。

$n$ 人がmodじゃんけんを $1$ 回行ってあいこになる確率を $p_n$ とするとき

$$
p_2=\frac{\fbox{ア}}{\fbox{イ}},\; p_3=\frac{\fbox{ウ}}{\fbox{エ}},\; p_4=\frac{\fbox{オ}}{\fbox{カキ}}
$$

である。$n$ を $\fbox{ク}$ で割った余りが $\fbox{ケ}$ であるとき

$$
p_n=\frac{\fbox{コ}^{n}+\fbox{サ}}{\fbox{シ}^n}
$$

であり,そうでないときには

$$
p_n=\frac{\fbox{コ}^{n}+\fbox{ス}}{\fbox{シ}^n}
$$

である。また,

$$
\lim_{n\to\infty} p_n=\fbox{セ}
$$

が成り立つ。

解答形式

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

求面積問題10

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

4

問題文

図中の赤い線分の長さが10のとき、青で示した四角形の面積を求めてください。

解答形式

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

[B] constant variable

Benzenehat 自動ジャッジ 難易度:
2年前

18

問題文

ある大きさの球から、ある直径の円柱をくりぬいた。円柱の軸は球の中心を通る。(ビーズのような形を想像してください)
この立体の体積が$36\pi$のとき、以下のうちいずれかの値が一意に定まる。

  1. 円柱の底面の半径
  2. 球の半径
  3. 円柱の深さ

一意に定まるものの番号と、その値を求めよ。

解答形式

一意に定まるものの番号を半角数字で1行目に、その値を2行目に入れてください。2行目は整数または既約分数で答えてください。

解答例

1
4

[C] coin tossing

Benzenehat 自動ジャッジ 難易度:
2年前

27

問題文

1円, 5円, 10円, 50円, 100円, 500円の硬貨が1枚ずつある。1回目の試行で6枚の硬貨を投げ、表が出た硬貨をもらうことができる。2回目の試行では、残った硬貨を投げ、やはり表が出た硬貨をもらうことができる。もらえる金額が600円以上になったらこの試行は終了するものとする。

(1) 1回目の試行で終わる確率はいくらか。
(2) 2回目の試行で終わる確率はいくらか。

解答形式

(1)の答えを1行目に、(2)の答えを2行目に既約分数で入れてください。

解答例

1/2
3/10

[A] minimum value (easy)

okapin 自動ジャッジ 難易度:
2年前

12

問題文

原点$O$とする$xy$平面上で点$(3,2)$を通る傾き負の直線と$x$軸,$y$軸との交点をそれぞれ$A,B$とするとき、$\triangle OAB$の面積の最小値を求めよ。

解答形式

整数または既約分数で答えてください。
半角で入力してください。

[B] Triangles 1

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

13

問題文

$k>0$ を整数の定数とする。以下の条件

$$
{\rm AB}=8, {\rm AC}=k, \angle {\rm ABC}=60^{\circ}
$$

を満たす三角形 ${\rm ABC}$ が存在するような整数 $k$ の最小値は $\fbox{\text{ア}}$ である。

また,条件を満たす三角形 ${\rm ABC}$ が一意的に存在するような整数 $k$ の最小値は $\fbox{イ}$ である。

ただし,互いに合同であるような $2$ つの三角形は区別しない。

解答形式

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

求値問題2

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

5

問題文

$△ABC$は鋭角三角形とします。次に、$A,B,C$から$BC,CA,AB$におろした垂線の足をそれぞれ$X,Y,Z$とし、$△ABC,△XYZ$の内接円の半径をそれぞれ$r,r'$とします。このとき、次の式の最小値を求めてください。
$$
\frac{r}{r'}\cos{\frac A2}\cos{\frac B2}\cos{\frac C2}
$$

解答形式

$$
\frac{r}{r'}\cos{\frac A2}\cos{\frac B2}\cos{\frac C2}\geq\frac{[ア]\sqrt{[イ]}}{[ウ]}=(最小値)
$$
となります。$[ア]+[イ]+[ウ]$を半角数字で解答してください。
ただし、$[ア],[イ],[ウ]$には自然数が入ります。また、分数部分は既約分数に、根号内の数字は最小となるようにしてください。

求長問題9

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

2

問題文

※2020.11.10 18:49 問題タイトルを修正しました。
(解答に影響はありません)

図中の線分ABの長さを求めてください。
緑で示した2つの三角形の面積の差は11,赤と青で示した線分の長さの差は1です。

解答形式

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

[C] 奇妙な数列

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

11

問題文

以下のような数列 $\{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$$

解答形式

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

[D] monotonous decrease

Benzenehat 自動ジャッジ 難易度:
2年前

12

問題文

$k$を$0$以上の実数, $e$を自然対数の底とする。数列$a_n$を
$$a_n=\frac{n!e^n}{n^{n+k}}$$
と定める。任意の自然数$n$に対して, $a_{n+1} < a_n$が成り立つような最小の$k$を求めよ。

解答形式

整数または既約分数で答えてください。

[A] よくある級数

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

8

問題文

$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行目に半角数字で入力せよ.