『离散数学 图论』证明n（n≥2）个人中

『离散数学 图论』证明n（n≥2）个人中，不认识另外奇数个人的人数是偶数。

热心网友

设A={1，2，。。。，n}，ak为k不认识的人数B={k，ak为奇数}C=A-B，Sn=∑{1≤k≤n}ak，1）n=1，Sn=0，为偶数。2）设S（n-1）为偶数，则设Dn={s，s和n不认识}，CardDn=an，有ak0，k在Dn设a'k=ak,k不在Dna'k=ak-1,k在Dn，由假设得S（n-1）=∑{1≤k≤n}a'k为偶数，所以Sn=S（n-1）+2an为偶数。3）Sn=∑{k在B}ak+∑{k在C}ak，∑{k在C}ak为偶数，则∑{k在B}ak，因为奇数个奇数和为奇数，所以B有偶数个数。所以不认识另外奇数个人的人数是偶数。

热心网友

用染色中的抽屉原理。

热心网友

如果你指的认识是单方的，那么等于2时不成立，有A、B两个人。A不认识B，但B认识B自己。只有A一个人啊？！