PUZZLEUP 2014

newkid

#15 Chess Players

There are 24 players in a chess tournament. 8 teams participated with 2 players , and 8 teams participated with 1 player. For the 12 matches in the first round, the pairings will be drawn randomly. What is the probability that at least 4 matches will be played between players from the same school?

Enter your answer as a simplified fraction. Example:12/23

棋手

共有24名选手参加国际象棋比赛。 8支队有2名选手参加，8支队以1名选手参加。 在第一轮的12场比赛，选手之间是随机配对的。
至少有四场比赛是在同一个学校的选手之间进行，这样的概率是多少？

将你的答案输入为简化分数，例如：12/23

-------------
就是一个比较复杂的排列组合题，估计每个人的答案都不一样!

newkid

配对方法总数：（分母）
C(24,2)*C(22,2)*C(20,2)*C(18,2)*C(16,2)*C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/12!
解释：每对即剩下人数中任选两人；最后除以12的全排列因为每组之间是无序的。

接下来凑分子，分为8组同校/7组同校/6组同校/5组同校/4组同校

恰好8组为同校：剩下四对任意配: C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!

恰好7组为同校：C(8,7)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
    --- 任选7对C(8,7), 剩下一对同校AB, A有8人可与之配对，解决A之后，最后剩下四对任意配对

恰好6组为同校：C(8,6)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!  
          --- 任选6对C(8,6), 剩下同校的两对AB,CD，假设A配了C, 则D有9人可配；A配了D, C也有9人可配。A如果不配CD，则有8人可配, CD中的任一人有8人可配。
          ---ABCD解决之后，最后剩下四对任意配对

恰好5组为同校：
   任选5组：C(8,5)
   剩下的所有7个配对：C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/7!
   应该排除情况：
       剩下7个配对中有三对同校: 剩下四对任意配: C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
       剩下7个配对中恰好两对同校: C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    --- 任选两对C(3,2), 剩下一个有8人可与之配对，最后剩下四对任意配对
       剩下7个配对中恰好一对同校: C(3,1)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    --- 任选一对C(3,1), 剩下同校的两对AB,CD，假设A配了C, 则D有9人可配；A配了D, C也有9人可配。A如果不配CD，则有8人可配, CD中的任一人有8人可配。
                    ---ABCD解决之后，最后剩下四对任意配对

   5组同校的最后公式：
   C(8,5)*(C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/7!
           -C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           -C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           -C(3,1)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           )

恰好4组为同校：
   任选四组：C(8,4)
   剩下的所有8个配对：C(16,2)*C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/8!
   应该排除情况：
       剩下8个配对中有四对同校: C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
       剩下8个配对中恰好三对同校: C(4,3)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    --- 任选三对C(4,3), 剩下一个有8人可与之配对，最后剩下四对任意配对
       剩下8个配对中恰好两对同校: C(4,2)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!  ---------- 有待SQL验证简化为ABCD+4人情况
                    --- 任选两对C(4,2), 剩下同校的两对AB,CD，假设A配了C, 则D有9人可配；A配了D, C也有9人可配。A如果不配CD，则有8人可配, CD中的任一人有8人可配。
                    ---ABCD解决之后，最后剩下四对任意配对
       剩下8个配对中恰好一对同校:
                    ---任选一对C(4,1), 剩下同校的三对AB,CD,EF, 不同校8人, 共14人
                    --- 14人所有配对情况：C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/7!
                    ---排除以下情况：
                    ---   14人中有三对同校：C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    ---   14人中有两对同校：C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    ---   14人中有恰好一对同校: C(3,1)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    ---综上所述公式：C(4,1)*(C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/7!
                                            -C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                                            -C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                                            -C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                                            )
   4组同校的最后公式：
    C(8,4)*(C(16,2)*C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/8!
           -C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           -C(4,3)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           -C(4,2)*(9*2+8*8)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
           -C(4,1)*(C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2)*C(4,2)*C(2,2)/7!
                    -C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    -C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    -C(3,2)*8*C(8,2)*C(6,2)*C(4,2)*C(2,2)/4!
                    )
           )

〇〇

newkid 发表于 2014-11-8 05:15
配对方法总数：（分母）
C(24,2)*C(22,2)*C(20,2)*C(18,2)*C(16,2)*C(14,2)*C(12,2)*C(10,2)*C(8,2)*C(6,2 ...

居然没有对手做题

lastwinner

newkid 发表于 2014-11-6 01:32
#15 Chess Players

There are 24 players in a chess tournament. 8 teams participated with 2 players ...

可以先简化考虑
4个人，2人一个学校，另外2人分别在两个学校
然后
6个人，两个学校，均2人参加，剩余2人分别在两个学校

这样比较好验证自己的思路

newkid

lastwinner 发表于 2014-11-9 02:10
可以先简化考虑
4个人，2人一个学校，另外2人分别在两个学校
然后

你来试试吧，后面的公式会越来越难。

lastwinner

newkid 发表于 2014-11-9 10:44
你来试试吧，后面的公式会越来越难。

是很麻烦，排列和组合混在一起了

“至少有四场比赛是在同一个学校的选手之间进行”，那么至少这四场的参赛者只能在 有2名选手的8支队中选人
(16/24*1/15)*(14/22*1/13)*(12/20*1/11)*(10/18*1/9)

因为是“至少”，所以仅四场、仅五场……仅八场的概率都包括在内了
结果心算有点麻烦，就不算了

lastwinner

lastwinner 发表于 2014-11-9 14:32
是很麻烦，排列和组合混在一起了

“至少有四场比赛是在同一个学校的选手之间进行”，那么至少这四场的 ...

(16/24*1/23)*(14/22*1/21)*(12/20*1/19)*(10/18*1/17)
似乎应该是这样才对

第一组，从24人的16人中任选一人，那么配对的必须是同校的，这概率是1/23
第二组，从剩下22人的14人中任选一人，配对正好是同校的概率为1/21
……

newkid

如果改成袋中摸球每次两个，题目问的是最终至少有四次两球同色的概率，你回答的是从第一次开始，连续四次两球同色的概率。
简化成四人，其中两人同校，两两分组后有一组同校的概率，应该是1/3而不是2/4*1/3

lastwinner

newkid 发表于 2014-11-9 22:36
如果改成袋中摸球每次两个，题目问的是最终至少有四次两球同色的概率，你回答的是从第一次开始，连续四次两 ...

嗯，对，4人的话，分组可能性：C(4,2)*C(2,2)/P(2,2)=3
最终是两个队，两个队中任意一队是同校的就行，所以C(2,1)=2，所以我的算法里最后还应该乘以一个2

如果是6人，来自4个队，其中两队是各有2人，分组可能性：C(6,2)*C(4,2)*C(2,2)/P(3,3)=15
至少有一对同校的概率实际是为1/3（假定12和34分别同校，56是两个学校）：
12 34 56 --
12 35 46 --  
12 36 45 --
13 24 56
13 25 46
13 26 45
14 23 56
14 25 36
14 26 35
15 23 46
15 24 36
15 26 34 --
16 23 45
16 24 35
16 25 34 --

按我的思路，这个结果应该这样推：
两对都同校，只有一种可能性，所以只有1种排法
至少有一对同校，排法应有：3+3-1=5 （扣除两对同时同校的可能性）


——————————————————————
后面感觉太复杂，不推了

newkid

#16 Colored Squares


You will color the 3x3 squares of a table with four colors

-All of the squares will be colored.
-All of the four colors will be used.
-A color will be used at most three times.
-The squares of the same color should form a single shape that is connected through vertically and horizontally adjacent squares.

What is the maximum number of different colorings that can be made according to these conditions?

Three of the valid colorings are shown above.

彩色方块



你将3×3的方块表格用四种颜色着色

- 所有的平方将被着色。
- 所有的四种颜色将被使用。
- 一种颜色将用于至多三次。
相同颜色的正方形所构成的形状，在垂直和水平方向都必须是相邻的方块所连接。

根据这样的条件最多可以有多少种不同的着色方法？

三个有效的着色方法的如上所示。



这个用递归WITH毫无压力。