【转帖】由红球、蓝球组成的金字塔有几种建造方案？

天山草

有大小相同的红球 15 个，蓝球 21个（共36个）。
将它们排成一个金字塔，如下图。要求如下：
（1）最上面一个球，最下面 8 个球，共排 8 层；
（2）最下层红球、蓝球各 4 个；
（3）红球下面的两个球，颜色必须相同（都是红球或者都是蓝球）；
（4）蓝球下面的两个球，颜色必须不同（一个红球，一个蓝球)。

问：共有几种不同的排列方案？（下图是其中一个符合要求的方案）

王守恩

从上往下找答案（不要从下往上找答案）。
1，1层是1个球：只能是1个红球（蓝球是不可能的）。
2，1层是2个球：只能是2个蓝球（红球是不可能的）。
3，1层是3个球：只能是2个蓝球+1个红球。
4，1层是4个球：只能是2个蓝球+2个红球。
5，1层是5个球：
..........

天山草

如果从最底层的 8 个球考虑，底层一旦确定下来，上面七层将自动确定。只要满足红球恰好是 15 个即可。底层红 4、蓝 4 的排列方案中，有些是可以排除掉的。比如 ●●●●○○○○ （实心球表示红球），再比如●●●○●○○○，因为最终红球会超过 15 个。根据这个启示，好像有办法了……

天山草

经编程寻找，只有下面这四种方案。

如果从金字塔背后看，跟从前面看的某一个图案相同（下面图 1 与图 4；图 2 与图 3），那么这两个算同一个方案的话，就只有两种方案了。



我的编程方法是：
如果最底层的 8 个球（4 红、4 蓝）排列方法确定，上面所有七层也就都确定了。而底层的排法只有 70 种，对于每一种底层图案，统计所有各层的红球数目，如果恰好等于 15，就找到了一种方案。

王守恩

王守恩 发表于 2017-5-21 05:32
从上往下找答案（不要从下往上找答案）。
1，1层是1个球：只能是1个红球（蓝球是不可能的）。
2，1层是2 ...

天山草先生的方法干净，利落。佩服！学习了。
底层的排法有70种，去掉翻转的32种，剩下也就38种了。
我的不行，让大家见笑！

我们称红球与蓝球之间的空隙为V，
1层是2个球的空隙简记为V(2)，
1层是3个球的空隙简记为V(3)，
1层是4个球的空隙简记为V(4)，
1层是5个球的空隙简记为V(5)，
1层是6个球的空隙简记为V(6)，
1层是7个球的空隙简记为V(7)，
1层是8个球的空隙简记为V(8)。
我们有
17个蓝球=V(2)+V(3)+V(4)+V(5)+V(6)+V(7)+V(8)
             =  0  +  2   +  2  +  2  +  ？ +  ？ +  ？
      即11=V(6)+V(7)+V(8)
            =  2   +  2  +  7
            =  2   +  4  +  5
            =  4   +  2  +  5
            =  4   +  4  +  3
排列分析，可知2+4+5，4+4+3满足题意。

天山草

用 VB 写的程序如下：

Private Sub form_Click()
     Open "金字塔方案有多少种.txt" For Output As #1
     Dim x(8) As String   
     x(1) = 11111111: x(2) = 1111111: x(3) = 111111: x(4) = 11111: x(5) = 1111: x(6) = 111: x(7) = 11: x(8) = 1     
     m = 8   '八位数
     n = 0
     For i = x(1) To x(1) + 10 ^ 10 '实际上达不到这么多循环。
         x(1) = x(1) + 1        '从最小的数字开始依次加 1，把不符合要求的去掉，符合要求者写入文件。
        For j = m To 2 Step -1 '将字符串变换成“二进制”串(由1，2 组成，不是由 0，1 组成)
         If Mid(x(1), j, 1) = 3 Then
           Mid(x(1), j, 1) = 1      '本位变为 2
           Mid(x(1), j - 1, 1) = 1 + Mid(x(1), j - 1, 1)   '高位加上进位 1
         End If
        Next j                                
        If Mid(x(1), 1, 1) = 3 Then GoTo 999 '控制结束的语句，最高位变成 3，则结束运行。     
         '以下筛选出符合要求的字串：
         a1 = 0  '底层的蓝球数目
       For j = 1 To 8 '
        If Mid(x(1), j, 1) = 1 Then a1 = a1 + 1
        Next j
        If a1 <> 4 Then GoTo 222  '底层的蓝球数目不等于 4 则跳过不用。                     
        For jj = 1 To 7
          For j = 1 To 8 - jj     '第二层至第八层的排法
           If Mid(x(jj), j, 1) <> Mid(x(jj), j + 1, 1) Then Mid(x(jj + 1), j, 1) = 1
           If Mid(x(jj), j, 1) = Mid(x(jj), j + 1, 1) Then Mid(x(jj + 1), j, 1) = 2
          Next j
        Next jj
      
        aa = 0  '以下统计所有层的蓝球数目        
        For jj = 1 To 8
         For j = 1 To 9 - jj     '统计第一层至第八层中所有蓝球的数目
          If Mid(x(jj), j, 1) = 1 Then aa = aa + 1
         Next j
        Next jj     
      If aa <> 21 Then GoTo 222  '各层的蓝球数目之和不等于 21 则跳过不用。      
      n = n + 1
      Print n; "=>"; Trim(x(1))
      Print #1, n; "=>"; Trim(x(1))      
222:  Next i
999:  Print " n ="; n
      Print #1, " n ="; n
      If n = 0 Then Print "无解！"
      Close
      End Sub

天山草

研究上述程序可以发现，此题的作者对问题是精心设计过的。有的条件如果不合适，将会导致无解；或是解有许多。例如红球数目为 16，蓝球为 20 个时，有 16 个解（去掉对称的仍有 8 个解）。

而当底层的蓝球数目是 5 个，蓝球总数仍是 21 时，有 18 个解（去掉对称的有 9 个解）。

王守恩

天山草 发表于 2017-5-21 22:06
研究上述程序可以发现，此题的作者对问题是精心设计过的。有的条件如果不合适，将会导致无解；或是解有许多 ...

给出38种排列，1代表红球，2代表蓝球。手工摆一摆，不是太难。
1，11112222
2，11121222
3，11122122
4，11122212
5，11122221
6，11211222
7，11212122
8，11212212
9，11212221
10，11221122
11，11221212
12，11221221
13，11222112
14，11222121
15，11222211
16，12111222
17，12112122
18，12112212
19，12112221
20，12121122
21，12121212
22，12121221
23，12122112
24，12122121
25，12211122
26，12211212
27，12211221
28，12212112
29，12221112
30，21111222
31，21112122
32，21112212
33，21121122
34，21121212
35，21122112
36，21211122
37，21211212
38，22111122

王守恩

天山草先生！题目变化一下，可以吗？

有大小相同的红球 20 个，蓝球 25个（共45个）。
将它们排成一个金字塔，如下图。要求如下：
（1）最上面一个球，最下面 9个球，共排 9 层；
（2）8个球那层是红球、蓝球各 4 个；
（3）红球下面的两个球，颜色必须相同（都是红球或者都是蓝球）；
（4）蓝球下面的两个球，颜色必须不同（一个红球，一个蓝球)。

问：共有几种不同的排列方案？

天山草

王守恩 发表于 2017-5-23 20:30
天山草先生！题目变化一下，可以吗？

有大小相同的红球 20 个，蓝球 25个（共45个）。

金字塔增加一层，共 9 层，从底层（第一层）往上数，第二层的 8 个球必须是 4 红 4 蓝。蓝球总和是 25个。
仍然要从最底层开始考虑，而不从第二层考虑，第二层的 4 红 4 蓝仅仅作为一个筛选条件。
那么最底层的蓝球是多少个呢？不是没有给出这个条件吗？没关系，最少是 1，最多是 9，依次考虑，只须把程序中的参数改一下再运行即可。
运行程序知：

底层蓝球数 = 1，无解；
底层蓝球数 = 2，无解；
底层蓝球数 = 3，无解；
底层蓝球数 = 4，若对称的不计入，有 2 解——底层是 112122221 和 112221221，这里 1 表示蓝球，2 表示红球；
底层蓝球数 = 5，若对称的不计入，有 3 解——底层是 112122211，121112221，211112212；
底层蓝球数 = 6，若对称的不计入，有 6 解——底层是 111121221，111122121，111211221，111221121，112111221，112211121；
底层蓝球数 = 7，无解；
底层蓝球数 = 8，无解；
底层蓝球数 = 9，无解。

因此，共有 11 个解（对称的解不计入）。
                                                                                                                        
以底层排列是 112122221 这个解为例，金字塔结构如下：
             2
            11
           121
          2112
         11211
        121121
       1221221
      21112221
     112122221

其中 1 表示蓝球，共有 25 个，2 表示红球，共有 20 个。红蓝共计 45 个。从下往上数第二层，红球蓝球各有 4 个。完全符合所有条件。