离散数学习题

问题:

一.20170920

问题:

在某班班委成员的选举中,已知王小红,李强,丁金生三位同学被选举进了班委会,该班的甲,乙,丙三名学生预言:
甲说:王小红为班长,李强为生活委员 。
乙说:丁金生为班长,王小红为生活委员 。
丙说:李强为班长,王小红为学习委员 。
班委会分工名单公布后发现,甲,乙,丙三人都恰好猜对了一半,问王小红,李强,丁金生各任何职(用等值等演求解)?

解答:

其实很简单…可是我太zz了…

不妨设

$p_{1}$:王小红为班长;

$p_{2}$:丁金生为班长;

$p_{3}$:李强为班长;

$q_{1}$:王小红为生活委员;

$q_{3}$:李强为生活委员;

$r_{1}$:王小红为学习委员.

设F为三人最终的职务.
$$
F \Leftrightarrow
((p{1}\land\neg q{3} )\lor(\neg p{1}\land q{3}))\land\((p{2}\land\neg q{1} )\lor
(\neg p{2}\land q{1}))\land\((p{3}\land\neg r{1} )\lor(\neg p{3}\land r{1}))\\Leftrightarrow
(p{1}\land \neg q{3}\land p{2}\land\neg q{1}\land p{3}\land\neg r{1})\lor\
(p{1}\land \neg q{3}\land p{2}\land\neg q{1}\land\neg p{3}\land r{1})\lor\
(p{1}\land \neg q{3}\land\neg p{2}\land q{1}\land p{3}\land\neg r{1})\lor\
(p{1}\land \neg q{3}\land \neg p{2}\land q{1}\land \neg p{3}\land r{1})\lor\
(\neg p{1}\land q{3}\land p{2}\land\neg q{1}\land p{3}\land\neg r{1})\lor\
(\neg p{1}\land q{3}\land p{2}\land\neg q{1}\land \neg p{3}\land r{1})\lor\
(\neg p{1}\land q{3}\land\neg p{2}\land q{1}\land p{3}\land\neg r{1})\lor\
(\neg p{1}\land q{3}\land \neg p{2}\land q{1}\land \neg p{3}\land r{1}) \\Leftrightarrow
\neg p{1}\land q{3}\land p{2}\land\neg q{1}\land \neg p{3}\land r{1}\Leftrightarrow1
$$
得证.

感谢 @钟璐 同学

二.20171003

问题:

$证明错位排列数D{n}满足: n为偶数当且仅当D{n}为奇数$

解答:

对n进行归纳.

$D_{0}=1$,n=0时命题为真。假设对一切小于n的自然数为真.

考虑关于$D{n}$的递推方程:
$$
D
{n}=(n-1)(D{n-2}+D{n-1})
$$
若n为偶数,那么n-1为奇数,n-2为偶数。

根据归纳假设,$D{n-1}为偶数,D{n-2}$为奇数,它们的和为奇数。

从而得到$D_{n}$为奇数。

反之,设$D_{n}$为奇数,假若n为奇数,那么n-1为偶数。

根据递推方程$D{n}也是偶数,与D{n}$为奇数矛盾。

虽然逻辑上能明白…但是真的可以这么写吗…

坚持原创技术分享,您的支持将鼓励我继续创作!