我知道这里藏龙卧虎,不但有作家、艺术家、音乐家,也有工程师、电脑分析师及数学家。这里有个数学问题想向诸位高人请教一下。如果您能请答案及分析过程(请用高中生能懂的语言)公布如下,我将感激不尽。如果您愿意“私了”,:) 将答案寄往本人电子邮箱亦可:虚风子 xufengzi@gmail.com。先谢谢大家的时间与参加!
------------------------------------------------------------------------------
在下列图案中有五个位置:1,2,3,4和5。这五个位置可用于放置英文字母。每个位置只能放一个字母。位置1和5, 2和4是对称的。
现有三套英文字母:第一套只有四个不同字母:A,B,C和D;第二及第三套字母相同:每套各有24个不同字母(A,B,C,D,E等直到X)。
各套间相同的字母是等值的(如第一套中的字母A与第二套中的字母A没有区别)。
由于图形的对称性,把一个字母放到图形的1位与5位,或2与4位将产生同样的图案。所以如果取第一套字母,每次一个字母放在图形上,一个图形只能有一个字母,一共只能有4 (字母数) X 3 (可能位置数) = 12种独特(或不重复)的图案。
问题:
(1) 在由第一套字母生成的12种独特图案上,如果再从第二套字母抽出字母来,一次只用一个字母,每个图案正好有二个字母,一共可以产生多少种独特(或不重复)的图案?
(2) 在由第一套字母生成的12种独特图案上,如果再分别从第二及第二套字母中一次各取一个字母,即一次将二个字母放在图案上(每次取出的两个字母可以重复,比如一次可用二个A),每个图案正好有三个字母, 一共可以产生多少种独特(或不重复)的图案?
注意各套间重复字母(即ABCD)的存在及图形位置的对称性,都会产生重复图案。
------------------------------------------------------------------------------
如有不清楚处,敬请提问。
第一位提供答案并经其它高手认证答案的高人将获“玛雅神算子”电子证书一份。^_^ 再次感谢!
- Re: 数学(排列组合)问题求教posted on 12/01/2008
do you have the problem in english - posted on 12/02/2008
在下列图案中有五个位置:1,2,3,4和5。这五个位置可用于放置英文字母。每个位置只能放一个字母。位置1和5, 2和4是对称的。
A graph (below) has five slots (1 through 5) into which English alphabetic letters may be placed. Each slot may only take one letter. Positions 1 and 4, 2 and 4 are symmetrical (as further explained below).
现有三套英文字母:第一套只有四个不同字母:A,B,C和D;第二及第三套字母相同:每套各有24个不同字母(A,B,C,D,E等直到X)。
Three sets of alphabetic letters are to be used. The first set consists of four unique letters: A, B, C and D; the second and third sets are the same: each consisting of 24 different letters (A, B, C, D, E and so forth through X).
各套间相同的字母是等值的(如第一套中的字母A与第二套中的字母A没有区别)。
Letters of the same kind in different sets are indistinguishable (for example, the letter A in the first set is the same as the letter A in the second set).
由于图形的对称性,把一个字母放到图形的1位与5位,或2与4位将产生同样的图案。所以如果取第一套字母,每次一个字母放在图形上,一个图形只能有一个字母,一共只能有4 (字母数) X 3 (可能位置数) = 12种独特(或不重复)的图案。
The symmetry of the graph also makes certain pattern arrangements indistinguishable. For example, a letter placed on position 1 is counted as the same arrangement or pattern as the letter placed on position 5. Similarly, a letter placed on position 2 or position 4 would create two indistinguishable patterns due to the symmetry. As a result, assuming that only one letter may be placed into one slot at a time and that each pattern may only contain one letter, the maximal number of possible patterns (unique or unrepeated) that may be formed using the first 4-letter set is 4 (the number of letters: A, B, C or D) x 3 (the number of possible positions: 1, 2 & 3 or 4, 5 & 3) = 12.
问题:
(1) 在由第一套字母生成的12种独特图案上,如果再从第二套字母抽出字母来,一次只用一个字母,每个图案正好有二个字母,一共可以产生多少种独特(或不重复)的图案?
Questions:
(1) If into any one available slot of the 12 patterns (formed by the first four-letter set as described above) is added another letter from the second 24-letter set so that each pattern contains exactly two letters, what is the maximal number of possible patterns (unique or unrepeated) that may be created?
(2) 在由第一套字母生成的12种独特图案上,如果再分别从第二及第二套字母中一次各取一个字母,即一次将二个字母放在图案上(每次取出的两个字母可以重复,比如一次可用二个A),每个图案正好有三个字母, 一共可以产生多少种独特(或不重复)的图案?
(2) If into any available two slots of the 12 patterns (formed by the first four-letter set as described above) are added two additional letters, drawn from the second and third 24-letter set, respectively (the two letters may be of the same type: e.g., the letter A may be drawn from both sets simultaneously, resulting two A's being placed into two separate slots at once), such that each pattern contains exactly three letters, what is the maximal number of possible patterns (unique or unrepeated) that may be created?
注意各套间重复字母(即ABCD)的存在及图形位置的对称性,都会产生重复图案。
Note that repeated patterns (to be minimized) may result from shared common letters (i.e. A, B, C and D) in all three letter sets or from the graph symmetry.
noname wrote:
do you have the problem in english - Re: 数学(排列组合)问题求教posted on 12/02/2008
风子 wrote:
由于图形的对称性,把一个字母放到图形的1位与5位,或2与4位将产生同样的图案。所以如果取第一套字母,每次一个字母放在图形上,一共只能有4 (字母数) X 3 (可能位置数) = 12种独特(或不重复)的图案。
风子给澄清一下这个对称性,比如下面这两个算相同的图案吗?
1-A 2-B 3-C 4-D
5-A 2-B 3-C 4-D
算的话,第一组四个字母都用上我怎么数出24个图案?估计再往下做是没戏了:) - posted on 12/02/2008
The two patterns you provided below would be considered the same.
For the first set, the rule is that you may only use one letter at a time. Therefore, 12 would be the max and the two separate, although related, questions are based on the 12 patterns created that way.
Thanks for taking the time to help me out on this. Please keep working on it, as you are definitely one of the few I'm counting on in my mind. :)
浮生 wrote:
风子 wrote:风子给澄清一下这个对称性,比如下面这两个算相同的图案吗?
由于图形的对称性,把一个字母放到图形的1位与5位,或2与4位将产生同样的图案。所以如果取第一套字母,每次一个字母放在图形上,一共只能有4 (字母数) X 3 (可能位置数) = 12种独特(或不重复)的图案。
1-A 2-B 3-C 4-D
5-A 2-B 3-C 4-D
算的话,第一组四个字母都用上我怎么数出24个图案?估计再往下做是没戏了:) - posted on 12/02/2008
进一步说明有关细节:
用第一套字母时每次只能抽一个,环上一次也只能有一个字母。所以共有12可能:
A1, A2, A3
B1, B2, B3
C1, C2, C3
D1, D2, D3
问题(1) 实际上是问,在上述12种图中,如果每图再加入一个字母(也只能加入一个字母)到环上,使环上正好有两个字母。 第二套字母(共24个)全部用完,有多少不重复的图?
问题(2) 实际上是问,在上述12种图中,如果每图再加入二个字母(也只能加入二个字母)到环上,使环上正好有三个字母。 第二、三套字母(共48个)全部用完,有多少不重复的图?
对先前有叙述不准确、不清楚处,在此道歉。 - posted on 12/02/2008
风子兄,这个问题我看了,暂时解不出来。主要是如何处理字母重复问题(每组都有a,b,c,d )没形成思路。
----------
我的解题思路是,先求4对字母组合数,答案是字母组合数乘12.
(1)
(一)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D不同。
24*23*22*21=225024
(二)a,b,c,d与a,b,c,d,e,.....x可构成多少个相同的4对字母组合。
0
由于第一套只有4个字母,目标又是4对字母的组合,重复的组合数是0。
=
(三)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D相同。
225024-0=225024
(四)结论
24*23*22*21**12=225024*12=2,700,288
---------------------
(2)
(一)a,b,c,d与A,B,C,D,E,.....X构成的4对字母组合数相同,不管a与A,b与B,c与C,d与D相同还是不相同。
(二)225024个4对两字母组合与a,b,c,d,e,.....x构成的4对三字母组合数为
(24*23*22*21)*(24*23*22*21)==225024*225024=50,635,800,576
(三)结论
(24*23*22*21)*(24*23*22*21)*12=607,629,606,912 - Re: 数学(排列组合)问题说明posted on 12/02/2008
(1) 17915904
- posted on 12/02/2008
(1) 708
此题相当于在五个位置任放两个字母,若两字母相同,有5种图案:
15,24,12,13,23
若两字母不同,有8种图案:
15,24,12,21,13,31,23,32
现在从两组字母中各取一个,构成相同字母的有4组(AA,BB,CC,DD);构成不同字母的分两种情况:ABCD和ABCD,有4 choose 2 = 6组,ABCD和E-X,有4x20=80组。所以图案总数为
5x4+8x(6+80) = 708
(2) 17824
数法如(1),五个位置任放三个字母,图案数分别为:
相同字母:5
二同一异:11
全不相同:18
从三组字母中各取一个,组合数分别为:
全部相同:4
二同一异:4x23(2A-D)+4x20(2E-X) = 172
全不相同:4(A-D choose 3)+6x20(A-D choose 2, E-X choose 1)+4x20x19/2(A-D choose 1, E-X choose 2) = 884
图案总数 = 5x4+11x172+18x884 = 17824
数得比较麻烦,不保证对了,特别是2,有没有简单些的数法? - Re: 数学(排列组合)问题说明posted on 12/02/2008
浮生 wrote:
(2) 17824
数法如(1),五个位置任放三个字母,图案数分别为:
相同字母:5
二同一异:11
16? I guess you missed A2A4B{1,3} and A2A3B{1,4,5}
全不相同:18
30? - posted on 12/02/2008
Part 1:
只放一个字母。1和5等价,2和4等家,因此这个图形等价于一行三个圆圈
---o(1/5)---o(2/4)---o
因此总共有3 x 4 = 12种可能。
注意1/5, 2/4的特殊性。
Part 2:
放两个字母。位置3比较特殊,因此分成两类:
第一个字母位于3时——有4种选择,剩余的两个位置(1/5和2/4)可以从24个里面任取1个,因此有4 x 24种组合。
第一个字母不位于3时——有2 x 4种选择,另一个字母可以放在任何一个位置,因此有3 x 24种选择,总的组合数是。
答案是两者相加:
4 x 24 + 2 x 4 x 3 x 24 = 672
Part 3:
放三个字母。
第一个字母位于3时——4 x 24 x 24
第一个字母不位于3时——2 x 4 x [ ]. 这个[ ]需要如下考虑:
其中一个字母位于3——24种,另一个2 x 24种
两个字母都不位于3——2 x 24种
答案是
4 x 24 x 24 + 2 x 4 x [24 x 2 x 24 + 2 x 24] = 11904
不知道对不对。 - posted on 12/02/2008
行人 wrote:
浮生 wrote:16? I guess you missed A2A4B{1,3} and A2A3B{1,4,5}
(2) 17824
数法如(1),五个位置任放三个字母,图案数分别为:
相同字母:5
二同一异:11
我是这么数的:三个位置共有5种可能: 152(or 154), 124(or 524), 153, 243, 123(or 143,523,543) , 括号内为equivalent cases。
前四种因15,24的对称性是同一种数法,不对称的位置如2in152有两种可能;最后的123各自unique,所以有3种可能,总数=4x2+3=11。
全不同的case是,前四种在不对称位置各有3种可能,123有3!种可能,所以总数 = 4x3+6=18。
全不相同:1830?
- Re: 数学(排列组合)问题求教(更正与澄清)--多谢赐教posted on 12/02/2008
J. wrote:
Part 2:
放两个字母。位置3比较特殊,因此分成两类:
第一个字母位于3时——有4种选择,剩余的两个位置(1/5和2/4)可以从24个里面任取1个,因此有4 x 24种组合。
consider 3A, then 1A
第一个字母不位于3时——有2 x 4种选择,另一个字母可以放在任何一个位置,因此有3 x 24种选择,
and consider 1A then 3A.
- posted on 12/03/2008
风兄,这是我的解答。
我的解题思路是,先求4对字母组合数,答案是字母组合数乘12.
我对这解答很有信心哈,请风兄一定公布正确答案。
(1)
(一)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D不同。
24*23*22*21=225024
(二)a,b,c,d与a,b,c,d,e,.....x可构成多少个相同的4对字母组合。
0
由于第一套只有4个字母,目标又是4对字母的组合,重复的组合数是0。
=
(三)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D相同。
225024-0=225024
(四)结论
24*23*22*21**12=225024*12=2,700,288
---------------------
(2)
(一)a,b,c,d与A,B,C,D,E,.....X构成的4对字母组合数相同,不管a与A,b与B,c与C,d与D相同还是不相同。
(二)225024个4对两字母组合与a,b,c,d,e,.....x构成的4对三字母组合数为
(24*23*22*21)*(24*23*22*21)==225024*225024=50,635,800,576
(三)结论
(24*23*22*21)*(24*23*22*21)*12=607,629,606,912
- posted on 12/03/2008
先再次感谢大家的参加与帮助。
不过我没有标准答案,因为这个问题不是从哪本书里或网上搬来同大家一起玩的。不过正因为没有标准答案,所以大家可以来一起创造“标准答案。” 另外,这个数学问题其实是一个实际的问题。
数学确实很有趣,它不但可以玩,还可以解决实际问题。:)
我看到的几种解题思路都各有千秋。其中浮生的比较“通俗易懂” 。不过按她的思路我好象得到不一样的结果。现求证如下。
浮生在第二题里有三种情况:
相同字母:5
二同一异:11
全不相同:18
我想从第二题的第三种情况“全不相同” ,再到第二种情况(“二同一异”) ,最后到第一种情况(“相同字母”) 。我能到的答案分别是30、18与5。我的哪出了问题么?
全不相同:30
For example, in (1) X1, Y2 leads to three distinct patterns:Z3, Z4 and Z5 (i.e. Z may be at three different positions. Similarly, each of the other 9 arrangements has three distinct patterns.
二同一异:18
相同字母:5
浮生 wrote:
(2) 17824
数法如(1),五个位置任放三个字母,图案数分别为:
相同字母:5
二同一异:11
全不相同:18
从三组字母中各取一个,组合数分别为:
全部相同:4
二同一异:4x23(2A-D)+4x20(2E-X) = 172
全不相同:4(A-D choose 3)+6x20(A-D choose 2, E-X choose 1)+4x20x19/2(A-D choose 1, E-X choose 2) = 884
图案总数 = 5x4+11x172+18x884 = 17824
数得比较麻烦,不保证对了,特别是2,有没有简单些的数法 - posted on 12/03/2008
还以为风子在帮二凤做作业呢:)
风子 wrote:
我想从第二题的第三种情况“全不相同” ,再到第二种情况(“二同一异”) ,最后到第一种情况(“相同字母”) 。我能到的答案分别是30、18与5。我的哪出了问题么?
30相当于把三个位置做了排列(6),共有5个unique的选择,5x6。但因为15,24的对称性,排列就会double-counting。
举个例子,看你的第一个图Three Different Letters,rows (1) and (3), columns 1,2,4给出的两个图案,若是24(YZ)互换,因其对称性是不是一个图案?你的表里有很多类似的double counting。这个对称性的描述对我来说是最不intuitive的地方,也才有前边的疑问。我猜行人也是这样数的,我的数法在上边回行人的帖子里。 - posted on 12/03/2008
我明白了。看来是我没有说清楚。对称性不是绝对的。比如Y2Z4=Z2Y4, 但一但有了X1,这种对称就没有了。即X1Y2Z4 =/= X1Z2Y4。
可以想象对称轴在1,5之间的那条线上,那个六边盘可以绕那条线转动180度,所以可产生对称性。但如果有东西挂上去了,比如如果起始是X1,那么这个六边盘就没有任何原来没有X1时的对称性了。
不知这样解释清楚没有。或许这原是个很简单的题(对你们而言),被我说复杂了。
浮生 wrote:
还以为风子在帮二凤做作业呢:)
风子 wrote:30相当于把三个位置做了排列(6),共有5个unique的选择,5x6。但因为15,24的对称性,排列就会double-counting。
我想从第二题的第三种情况“全不相同” ,再到第二种情况(“二同一异”) ,最后到第一种情况(“相同字母”) 。我能到的答案分别是30、18与5。我的哪出了问题么?
举个例子,看你的第一个图Three Different Letters,rows (1) and (3), columns 1,2,4给出的两个图案,若是24(YZ)互换,因其对称性是不是一个图案?你的表里有很多类似的double counting。这个对称性的描述对我来说是最不intuitive的地方,也才有前边的疑问。我猜行人也是这样数的,我的数法在上边回行人的帖子里。 - Re: 数学(排列组合)问题说明posted on 12/03/2008
风子 wrote:
可以想象对称轴在1,5之间的那条线上,那个六边盘可以绕那条线转动180度,所以可产生对称性。但如果有东西挂上去了,比如如果起始是X1,那么这个六边盘就没有任何原来没有X1时的对称性了。
恩,这样的对称性就intuitive拉。哎,这个风子,I twisted my mind trying to get used to the other definition :)
容我慢慢再数哈。 - posted on 12/03/2008
谢谢老A、行人、pass-by、J等。
问题(2〕的答案上限不应高于 (4x3)x(24x4)x(24x3) = (3x4x24)^2 = (12x12x2)^2 = 288^2 < 300^2 = 90,000。
90,000 是忽略了对称、重复的结果。实际数只可能低于9万。
abc wrote:
风兄,这是我的解答。
我的解题思路是,先求4对字母组合数,答案是字母组合数乘12.
我对这解答很有信心哈,请风兄一定公布正确答案。
(1)
(一)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D不同。
24*23*22*21=225024
(二)a,b,c,d与a,b,c,d,e,.....x可构成多少个相同的4对字母组合。
0
由于第一套只有4个字母,目标又是4对字母的组合,重复的组合数是0。
=
(三)a,b,c,d与A,B,C,D,E,.....X的4对字母组合数是多少,假设a与A,b与B,c与C,d与D相同。
225024-0=225024
(四)结论
24*23*22*21**12=225024*12=2,700,288
---------------------
(2)
(一)a,b,c,d与A,B,C,D,E,.....X构成的4对字母组合数相同,不管a与A,b与B,c与C,d与D相同还是不相同。
(二)225024个4对两字母组合与a,b,c,d,e,.....x构成的4对三字母组合数为
(24*23*22*21)*(24*23*22*21)==225024*225024=50,635,800,576
(三)结论
(24*23*22*21)*(24*23*22*21)*12=607,629,606,912
- posted on 12/03/2008
对称为轴对称。字母组合如前。
(1) 884
五个位置任放两个字母,unique图案数分别为:
相同字母:6 (12, 13, 14, 15, 23, 24)
不同字母:10
总数 = 6x4+10x(6+80) = 884
(2) 29296
五个位置任放三个字母,unique图案数分别为:
相同字母:6 (123, 124, 125, 134, 135, 234)
二同一异:16
全不相同:30
总数 = 6x4+16x172+30x884 = 29296
Wait, I need more clarification on the symmetry. Are patterns 1A4A and 2A5A same or not? I'm treating them as the same.
还很好奇风子这个问题的原型是什么?估计你不能说,我猜一个哈,是不是什么分子合成?那个六边行是苯环,A-D四个字母是氢水氨之类的,E-X二十个字母是氨基酸?嘿嘿,不好意思,我的高中有机都还回去拉就瞎说了。
- Re: 数学(排列组合)问题求教(更正与澄清)--多谢赐教posted on 12/03/2008
wa,你们都好厉害。。我是下班就懒得动用逻辑思维了。。 - Re: 数学(排列组合)问题求教(更正与澄清)--多谢赐教posted on 12/03/2008
浮生 wrote:嘿嘿,我也在ADD这个问题,估计是有关药物的专利?风子做专利法方面的工作?
还很好奇风子这个问题的原型是什么?估计你不能说,我猜一个哈,是不是什么分子合成?那个六边行是苯环,A-D四个字母是氢水氨之类的,E-X二十个字母是氨基酸?嘿嘿,不好意思,我的高中有机都还回去拉就瞎说了。
- posted on 12/04/2008
再次谢浮生。
我觉得昨天用的那张图“THREE DIFFERENT LETTERS”应该能包括所有情况。
浮生 wrote:
对称为轴对称。字母组合如前。
(1) 884
五个位置任放两个字母,unique图案数分别为:
相同字母:6 (12, 13, 14, 15, 23, 24)设上图里X=Y, 忽略Z, (1)-(6)正好六种 (因为(7)至(10)与上面有重复)。
不同字母:10
设上图里X =/= Y, 忽略Z, (1)-(10)正好10种。
总数 = 6x4+10x(6+80) = 884
(2) 29296设上图中 X=Y=Z, (1), (2)(2位不算) 加 (5) (去掉1、5位),也是六种排列。我昨天少算了一个。
五个位置任放三个字母,unique图案数分别为:
相同字母:6 (123, 124, 125, 134, 135, 234)
二同一异:16设上图中 X=Y=/=Z, (1), (2) ,(3), (4) (去2或4位), (5), (6) (去5位)。共18-2=16 (我昨天多算了二个 :)
全不相同:30全图共30种。
下一步就是看抽样种数对不对了。
总数 = 6x4+16x172+30x884 = 29296
Wait, I need more clarification on the symmetry. Are patterns 1A4A and 2A5A same or not? I'm treating them as the same.
对的,它们是对称的。
还很好奇风子这个问题的原型是什么?估计你不能说,我猜一个哈,是不是什么分子合成?那个六边行是苯环,A-D四个字母是氢水氨之类的,E-X二十个字母是氨基酸?嘿嘿,不好意思,我的高中有机都还回去拉就瞎说了。
这个原型问题比较复杂,我们还现把这个“简单”的数学问题解决了,再慢慢谈吧。:) - posted on 12/04/2008
浮生的答案应该是正确的。
这是我昨天凌晨收到的另一套答案。与浮生的答案正好一致。
我把纯分析的解答公布如下:
(1) 可分三种情况讨论:
1' 从第二套抽出的不是A,B,C,D, 则有4 X 20 X (A3^2 + A2^2 + 2) =
800种;
2'
从第二套抽出的是A,B,C,D但不与原来的(第一套)字母一样,则有
C4^2 X (A3^2 + A2^2 + 2) = 60种;
3' 从第二套抽出的是A,B,C,D且与原来的字母一样,则有C4^1 X
(C3^2 + 1 +2)
= 24种.
故共有800 + 60 + 24 = 884种.
(2) 可分7种情况讨论:
1' 从第二,第三套抽出的都不是A,B,C,D,且互不相同,则有
C20^2 X 4 X (A3^3 + A3^3 + C2^1 X C3^2 X 3) = 22800种;
2' 从第二,第三套抽出的都不是A,B,C,D,且为相同字母,则有
20 X 4 X (C3^1 + C3^1 + C2^1 X 2 + C2^1 X 3) = 1280种;
3'
从第二,第三套抽出的字母中只有一个是A,B,C,D且与原来的字母不同,则有
C4^2 X 20 X (A3^3 + A3^3 + C2^1 X C3^2 X 3) = 3600种;
4' 从第二,第三套抽出的字母中只有一个是A,B,C,D且与原来的字母相同,则有
C4^1 X 20 X (C3^1 + C3^1 + C2^1 X 2 + C2^1 X 3) = 1280种;
5' 最后在环上的三个字母都是A,B,C,D且两两互不相同,则有
C4^3 X (A3^3 + A3^3 + C2^1 X C3^2 X 3) = 120种;
6' 最后在环上的三个字母都是A,B,C,D且其中两个相同并与第三个不同,则有
C4^2 X 2 X (C3^1 + C3^1 + C2^1 X 2 + C2^1 X 3) = 192种;
7' 最后在环上的三个字母都是A,B,C,D且为同一字母,则有
C4^1 X (1 + 1 + C2^1 X 2) =24种.
故共有22800 + 1280 + 3600 + 1280 + 120 + 192 + 24 = 29296种.
Please paste HTML code and press Enter.
(c) 2010 Maya Chilam Foundation