|
|
kuing
Posted at 2017-5-29 17:29:43
可以利用 kuing.cjhb.site/forum.php?mod=viewthread&tid=4099 里的方法。
本题与那帖中的题的区别在于，帖中的题目限定了 0 和 1 的个数相同，而这里却没这个限制，不过方法显然还是能用。
根据那帖的方法易知，在方形网格中，若 $m$, $n\inN^+$, $m\geqslant n$，则由 $(0,0)$ 到 $(m,n)$ 且恒满足 $y\leqslant x$ 的最短路径总数为 $C_{m+n}^n-C_{m+n}^{n-1}$。
回到本题的情形中，若染色的格子数为 $2n$，则转化后等价于由 $(0,0)$ 到直线 $x+y=2n$ 上的格点且恒满足 $0\leqslant y\leqslant x$ 的最短路径总数。
根据上述结果，当终点为 $(n+k,n-k)$（$0\leqslant k\leqslant n-1$）时的数目为 $C_{2n}^{n-k}-C_{2n}^{n-k-1}$，而终点为 $(2n,0)$ 时只有 1 条，于是求和后，总数就是 $C_{2n}^n$。
同理，若格子数为 $2n-1$，则总数为 $C_{2n-1}^{n-1}$，将两种情况合起来，最终结论就是：若格式数为 $n$，则总数为 $C_n^{\lfloor n/2\rfloor}$。
所以本题第二问的结果就是 $C_6^3/2^6=5/16$。 |
|
isee
Posted at 2017-5-29 16:50:06
