問題一覧 | ポロロッカ

[F]Without Triangles

wa1t_sush1 自動ジャッジ難易度:

4年前

0

問題文

問題に不備がある可能性があるため、他の問題を先に解くことをおすすめします。申し訳ございません。ただいま確認作業を行っております。（18:31）

グラフとは，頂点集合とそのうち $2$ 点を結ぶ辺の集合のことである。今回は単純グラフ（同じ頂点を結ぶ $2$ 辺が存在しない場合）のみを考える。

$2n$ 頂点で三角形が存在しない，すなわちどの頂点集合 ${a, b, c}$ を選んでもすべてが辺によって結ばれていることはないようなグラフの辺数の最大値を求めよう。

まず，各頂点 $i\;(i=1,2,\cdots, 2n)$ に $\displaystyle{\sum_{i=1}^{2n}}v_i=1$ となるように非負実数 $v_i$ を割り当てる。この制約のもとで，

$$
S:=\sum_{\substack{\{i,j\}が辺で \\ 結ばれている}} v_iv_j
$$

を最大化することを考える（編注：和は辺で結ばれている頂点 $i, j\;(1\leq i < j\leq 2n)$ すべてにわたることを意味する）。

$$
X_x:=\sum_{\substack{\{x,i\}が辺で \\ 結ばれている}} v_i
$$

とする。次のような操作をくり返す。

操作
辺によって結ばれていない $2$ 頂点 $i,j$ について，$\fbox{ア}$ ならばある正の実数 $\varepsilon$ を選んで $v_i \mapsto v_i+\varepsilon$，$v_j\mapsto v_j-\varepsilon$ という置き換えを行う。ただし $\varepsilon$ は置き換え後も $v_1+\cdots+v_{2n}=1$ かつ $v_1, \cdots, v_{2n}\geq 0$ が成り立つようにとる。

操作をくり返すと，$(X_i+\varepsilon)v_i+(X_j-\varepsilon)v_j$ と $X_iv_i+X_jv_j$ の値を比較することで $S$ は必ず $\fbox{イ}$ ことが分かる。これ以上操作を行っても $S$ の値が変化しないような状態に達したときを考えると，$\fbox{ウ}$ となるような任意の $2$ 点 $i,j$ どうしは辺で結ばれている。グラフが三角形を含まないことから，このとき

$$
S\leq \fbox{エ}
$$

である（編注：等号が成立するグラフが存在するように選ぶこと）。はじめ，すべての $v_i$ が等しかったとすると，操作を行う前は

$$
S=\frac{（辺の本数）}{\fbox{オ}}
$$

なので，（辺の本数）$\leq \fbox{カ}$ が分かる。

等号は $2n$ 頂点が $n$ 頂点の組 $2$ つに分かれていて，異なる組に属している場合のみ辺が存在するようなグラフで成り立つ。よって最大の辺数は $\fbox{カ}$ である。

$\fbox{ア}$ 〜 $\fbox{カ}$ に最もよく当てはまるものを，次の選択肢の中からそれぞれ選びなさい。

選択肢

$\fbox{ア}$ の選択肢：

1$\;v_i\leq v_j$　2$\;v_i\geq v_j$　3$\;X_i\geq X_j$　4$\;X_i\geq X_j$

$\fbox{イ}$ の選択肢：

1 変化しないか増加する　2 変化しないか減少する

$\fbox{ウ}$ の選択肢：

1$\;v_i>0, v_j>0$　2$\;v_i=0, v_j=0$　3$\;X_i>0, X_j>0$　4$\;X_i=0, X_j=0$

$\fbox{エ}$ の選択肢：

1$\;n^2$　2$\;\cfrac{n^2}{2}$　3$\;\cfrac{n^2}{4}$　4$\;1$　5$\;\cfrac{1}{2}$　6$\;\cfrac{1}{4}$

$\fbox{オ}$ の選択肢：

1$\;n^2$　2$\;2n^2$　3$\;4n^2$　4$\;1$　5$\;4$

$\fbox{カ}$ の選択肢：

1$\;n^2$　2$\;\cfrac{n^2}{2}$　3$\;2n^2$　4$\;n^4$

解答形式

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

[D] Along the Edges

hinu 自動ジャッジ難易度:

4年前

8

問題文

$$
\newcommand{\nc}{\newcommand}
\nc{\wake}[1]{\begin{cases} #1 \end{cases}}
\nc{\f}[2]{\dfrac{#1}{#2}}
\nc{\s}[1]{\{#1\}}
\nc{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}}
\nc{\lr}[1]{\left( #1 \right)}
\nc{\com}[2]{{}_{#1}{\rm C}_{#2} \right)}
\nc{\bar}[1]{{\overline{#1}}}
\nc{\bb}[1]{{\mathbb {#1}}}
\nc{\rmn}[1]{{\rm #1}}
\nc{\q}{\quad}
\nc{\x}{\times}
\nc{\a}{\alpha}
\nc{\b}{\beta}
\nc{\th}{\theta}
\nc{\Q}[1]{\fbox{#1}}
$$

下のように $\rm AB=1\ ,\ BC=2$ の長方形 $\rm ABCD$ がある。点 $\rm P$ は $t=0$ で点 $\rm A$ におり、 $1$ 秒間に $1$ の速度で辺の上を進む。点 $\rm P$ が点 $\rm A,B,C,D$ のいずれかにいるとき確率 $p$ で辺 $\rm AB$ に平行な向きに、 $1-p$ の確率で辺 $\rm AD$ に平行な向きに向きを変え、それ以外の場所で向きを変えることはないものとする。

$p=\dfrac56$ とするとき点 $\rm P$ が $2n$ 秒後 $(n=0,1,2,\cdots)$ に点 $\rm A$ にいる確率を求めたい。

点 $\rm P$ が $2n$ 秒後に点 $\rm A,D$ にある確率を $A_n,D_n$ とおく。このとき $X_n=A_n+D_n$ とおくと漸化式
$$
X_{n+1}=\f{\Q{ア}}{\Q{イ}}X_n +\f{\Q{ウ}}{\Q{エ}}
$$
が成り立つ。また $Y_n=A_n-D_n$ とおくと漸化式
$$
Y_{n+2}-\f{\Q{オ}}{\Q{カ}}Y_{n+1}+\f{\Q{キ}}{\Q{ク}}Y_n=0
$$
が成り立つ。これらを初期条件 $X_0=\Q ケ\ ,Y_0=\Q{コ}\ ,Y_1=\f{\Q{サ}}{\Q{シ}}$ のもとで解くことで
$$
A_n=\f{\Q ス}{\Q セ}+\f{\Q ソ}{\Q タ}\lr{\f{\Q チ}{\Q ツ}}^n-\lr{\f{\Q テ}{\Q ト}}^n+\f{\Q ナ}{\Q ニ}\lr{\f{\Q ヌ}{\Q ネ}}^n
$$
を得る。なお ${\f{\Q チ}{\Q ツ}}<{\f{\Q ヌ}{\Q ネ}}$ である。

解答形式

上の空欄を埋めよ。解答は半角数字・改行区切りで入力すること。ただし $\Q ア$ から $\Q ネ$ にはそれぞれ 1 から 999 までの整数が入り、分数は既約分数の形で表してある。

[B] Ising Othello

ofukufukufuku 自動ジャッジ難易度:

KOH-MC

4年前

6

問題文

片面が黒色、もう片面が白色のオセロが一直線に$N$個並んでいる。1秒経過するごとに，$N$個のオセロから無作為に1つ選び裏返す。

時刻$t(\geq0)$における黒色のオセロの個数を$A_N(t)$で表すとする。$A_4(0)=2$のとき$A_4(2)=2$となる条件付き確率を$P_1$，$A_8(0)=2$のとき$A_8(3)=3$となる条件付き確率を$P_2$とすると，
$$
P_1=\frac{\fbox{ア}}{\fbox{イ}},~~~~P_2=\frac{\fbox{ウ}}{\fbox{エ}}
$$である.

時刻$t(\geq0)$における$A_N(t)$の期待値を$\mu_N(t)$とすると，以下の漸化式が成立する。
$$
\mu_N(t+1)=\left(\fbox{オ}-\frac{\fbox{カ}}{\fbox{キ}}\right)\mu_N(t)+\fbox{ク}
$$これより，
$$
\lim_{t\to\infty}\mu_{50}(t)=\fbox{ケ}
$$となる。