ＢＥＧＩＮ

おはにゃ。 やること 実数列のなす実ベクトル空間 $V = \mathbb{R}^\mathbb{N}$ に、可算濃度の基底が存在しないことを示します。 きもち 手法としては、対角線論法に近いです。 基底のどんな有限部分集合 $S$ に対しても、その線形結合で書けない部分を含む数列を用意したいです。 $S$ は自然数で添字付けられているので、 これを Gödel コーディングのノリで自然数に対応付けましょう。 $S$ のコードを $n_S$ としたとき、 $S$ のどんな線形結合をとっても、$(b_1, b_2, \cdots, b_{n_S})$ の部分を表せないようにできます。 やります …

シミュレーションするか、ソートするかによって解ける典型問題！ 問題へのリンク 問題概要 人の髪の長さは最初 であった。 各人の髪の長さは 1 日に 1 ずつ伸びる。 初めて髪の長さが 以上の人が 人以上となるのは何日後かを求めよ。 制約 解法 (1)：シミュレーション まず、最初の解法は単純にシミュレーションすることです。 後について、髪の長さを 1 ずつ増やしていき、髪の長さが 以上である人数を数えていこう。 この人数が 人以上となった瞬間の日数を答えればよい。 コード #include <bits/stdc++.h> using namespace std; int main() { in…

Roth and Vande Vate (1990)「安定マッチングへの道は常に開かれていますよ」 以下では、Roth と Vande Vate による 1990年 の論文に於ける主定理の証明を紹介します。 マッチング理論に於ける一般的な概念の定義は最下部で行います。 マッチング理論の概念に触れたことのない方は、先にそちらを読んでいただけるとよいと思います。 読む論文 Roth, A. E., & Vate, J. H. V. (1990). Random paths to stability in two-sided matching. Econometrica: Journal of th…