【102 个组合数学问题】选载

elim

问题3 这 \(n > 1\) 是奇数, 试证 \(\binom{n}{1},\,\binom{n}{2},\ldots,\binom{n}{\frac{n-1}{2}}\) 中有奇数个奇数.

elim

问题4正整数 1 到 2001 中有多少数是 3 或 4 的倍数却不是 5 的倍数？

附上pdf 原文. 可隨意下載，翻譯其中的問題貼在這裏。也可分享您的解答。
刚才发现这个681Kb的pdf含理论概括，题目解答和参考书目. 简直就是组合教程.

elim

问题3 这 \(n > 1\) 是奇数, 试证 \(\binom{n}{1},\,\binom{n}{2},\ldots,\binom{n}{\frac{n-1}{2}}\) 中有奇数个奇数.
解：\(\because\;\displaystyle {\small\binom{n}{k}=\binom{n}{n-k}\implies 2\big(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{\frac{n-1}{2}}\big)=\sum_{k=0}^n\binom{n}{k}=}2^n\)
\(\quad\therefore\;\;{\small\displaystyle\binom{n}{1}+\binom{n}{2}+\cdots\binom{n}{\frac{n-1}{2}}}=2^{n-1}-1(>1)\) 是奇数.\(\\\)
\(\quad\therefore\;\;\)上式左边奇数加项的个数是奇数.\(\quad\square\)

elim

问题4 正整数 1 到 2001 中有多少数是 3 或 4 的倍数却不是 5 的倍数？
解：令 \(\small E(j)=\{k\in\mathbb{N}: \,j\mid k\le 2001\},\;A=E(3),\;B=E(4), C=E(5).\)
\(\quad\)则 \(\small|A|=\lfloor{\small\dfrac{2001}{3}}\rfloor=667,\,|B|=500,\;|A\cap C|=\lfloor{\small\dfrac{2001}{3\times 5}}\rfloor=133,\)
\(\quad\small|B\cap C|=100,\,|A-C|=|A|-|A\cap C|=534,\; |B-C|=400,\)
\(\quad\small|(A\cap B)-C|=|A\cap B|-|A\cap B\cap C|=166-33=133.\) 代入下式:
\(\quad\small|(A\cup B)-C|=|A-C|+|B-C|-|A\cap B-C|=801.\quad\square\)

注记：由集合并,交,差及\(\small A,B,C\)的定义, \(\small |(A\cup B)-C|\) 就是本题所要求的数。
\(\quad\)这个算法比较抽象，似乎难以信服。我们用 python 编程来验证之：

elim

问题5 将\(\small 1,2,3,\ldots,999\) 连接起来构成一个纯小数
\(\quad\; x\small =0.123456789101112131415161718\ldots 998999.\)
\(\quad\)求小数点后第1983位之数码.
解：\(\small 1\sim 9\)占\(\small 9\)位, \(\small 10\sim 99\)占\(\small 180\)位. 所剩 \(\small 1983-189=1794\)位由最初
\(\small 1784/3=598\)个三位数即\(\small 100\sim 697\)填满. 故\(x\)小数点后第1983位是\(\small 7.\)

elim

问题6 25个男生25个女生围坐成一圈。试证必有某同学的两边都是女同学.
证： 我们把男生用黑珠子替代，女生用白珠子替代，问题可以简化成把2n+1对黑白珠子打乱串成一个环，须证必有一个珠子，与之相邻的都是白珠。任取一个这种环，如果有某个黑珠两侧都是白珠，那么命题已证实. 否则黑珠必在环中成队出现，设有m队黑珠，每队由相继的\(k_j\)个黑珠构成,,\(k_j\ge 2,\;j=\overline{1,m}\). 它们被m个白珠串隔开。若各白珠串长度均\(\le 2\), 白珠总数\(\le 2m\); 但黑珠总数是奇数\(> 2m\). 男女失衡. 所以在题设条件下，若没有男生两侧都是女生，必有某白珠串含\(>2\)个珠子，即有某女生两侧皆女生。\(\space\square\)

注：二楼附的 pdf 教程有不同的证法，值得学习。