跳舞问题

跳舞问题.tex

\documentclass[UTF-8]{ctexart}
\usepackage{amsmath}

\title{跳舞问题}
\author{billchenchina}
\date{\today}
\begin{document}
    \maketitle
    \section*{问题描述}
    毕业舞会上，小伙子与姑娘跳舞。已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过舞。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。
    
    证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，二者两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。

    \section*{一种解法}
    设男生集合为F，女生集合为G。
    
    要想证明此问题，只需\(\exists{(f_i, f_j)}\)，使得\(\exists{(x, y)}\)，\(g_{i_{x}}\notin G_j\)、\(g_{j_{y}} \notin G_i\)。

    即只需证明\(G_i \not\subseteq G_j\)且\(G_j \not\subseteq G_i\)。

    假设不存在\((f_i, f_j)\)，使得\(G_i \not\subseteq G_j\)且\(G_j \not\subseteq G_i\)，则存在一种顺序\(w_i\)使得\( \emptyset \neq G_{w_1} \subseteq G_{w_2} \subseteq  G_{w_3} \subseteq \cdots \subset G\)

    由于所有女生都跳过舞，即 \(\cup G_i = G\)，矛盾。

    所以原命题成立。

\end{document}