Question

离散数学中集合与图论的简单问题，帮下哈 谢谢！

1.设f=ugv,其中f,g,u,v都是从集合A到A的映射，证|f(A)|<=|g(A)|
2.毕业舞会，男生和女生跳舞，已知每个男生至少与一个女生跳过舞，但未能与所有女生跳过舞。同样，每个女生也至少与一个男生跳过舞。证明：在所有参加舞会的女生与男生中，必可找到两个女生和男生，这两个女生中的每一个只与这两个男生中的一个跳过舞，而这两个男生中的每一个也只与这两个女生中的一个跳过舞。（用容斥原理）

Answer 1

1复合映射的值域一定小于每一个映射的值域（指的是元素个数，不一定有包含关系）
2其实命题很弱。只要证明存在两个男生A、B，他们所认识的女生集合不互相为包含关系，就一定可以各选出一个A认识而B不认识的女生和B认识A不认识的女生组成满足条件的四人组。反证法，如果这个条件不成立的话，那么所有的男生所认识的女生一定是互为包含关系，则一定可以选出一个认识人最多的男生；这个男生不认识的女生就会不认识所有男生，与题中“每个女生也至少与一个男生跳过舞”矛盾。

大才女 *.*!