问一道高中竞赛组合题考察一个仅由数字1和2组成的100位数,允许从中挑出任意10个连续的数字,并将前5个与后5个数字的位置互换,如果一个100位数可以由另一个经过若干次上述操作而得到,则称
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/30 20:10:34
![问一道高中竞赛组合题考察一个仅由数字1和2组成的100位数,允许从中挑出任意10个连续的数字,并将前5个与后5个数字的位置互换,如果一个100位数可以由另一个经过若干次上述操作而得到,则称](/uploads/image/z/6073864-16-4.jpg?t=%E9%97%AE%E4%B8%80%E9%81%93%E9%AB%98%E4%B8%AD%E7%AB%9E%E8%B5%9B%E7%BB%84%E5%90%88%E9%A2%98%E8%80%83%E5%AF%9F%E4%B8%80%E4%B8%AA%E4%BB%85%E7%94%B1%E6%95%B0%E5%AD%971%E5%92%8C2%E7%BB%84%E6%88%90%E7%9A%84100%E4%BD%8D%E6%95%B0%2C%E5%85%81%E8%AE%B8%E4%BB%8E%E4%B8%AD%E6%8C%91%E5%87%BA%E4%BB%BB%E6%84%8F10%E4%B8%AA%E8%BF%9E%E7%BB%AD%E7%9A%84%E6%95%B0%E5%AD%97%2C%E5%B9%B6%E5%B0%86%E5%89%8D5%E4%B8%AA%E4%B8%8E%E5%90%8E5%E4%B8%AA%E6%95%B0%E5%AD%97%E7%9A%84%E4%BD%8D%E7%BD%AE%E4%BA%92%E6%8D%A2%2C%E5%A6%82%E6%9E%9C%E4%B8%80%E4%B8%AA100%E4%BD%8D%E6%95%B0%E5%8F%AF%E4%BB%A5%E7%94%B1%E5%8F%A6%E4%B8%80%E4%B8%AA%E7%BB%8F%E8%BF%87%E8%8B%A5%E5%B9%B2%E6%AC%A1%E4%B8%8A%E8%BF%B0%E6%93%8D%E4%BD%9C%E8%80%8C%E5%BE%97%E5%88%B0%2C%E5%88%99%E7%A7%B0)
问一道高中竞赛组合题考察一个仅由数字1和2组成的100位数,允许从中挑出任意10个连续的数字,并将前5个与后5个数字的位置互换,如果一个100位数可以由另一个经过若干次上述操作而得到,则称
问一道高中竞赛组合题
考察一个仅由数字1和2组成的100位数,允许从中挑出任意10个连续的数字,并将前5个与后5个数字的位置互换,如果一个100位数可以由另一个经过若干次上述操作而得到,则称这两个数是合同的.问:至多可以选出多少个两两不合同的仅由1和2组成的100位数?
答案是21^5.但我觉得会有更多.
问一道高中竞赛组合题考察一个仅由数字1和2组成的100位数,允许从中挑出任意10个连续的数字,并将前5个与后5个数字的位置互换,如果一个100位数可以由另一个经过若干次上述操作而得到,则称
将100位分为5组:A1,A2,...,A5,其中Ai由第5k+i位组成,k = 0,1,2,...,19.
设Ai的20位中2的个数为ai,则ai的可能取值为0,1,2,...,20,共21种.
且对a1,a2,...,a5在此范围内的每一种,不难构造相应的100位数.
而易见题目中的操作不改变ai,因此合同的等价类至少有21^5个.
接下来说明等价类恰有21^5个,具体来说每个满足要求的100位都合同于"标准型".
这里"标准型"是指每个Ai都具有1,1,...,1,2,2,..,2形式.
考虑如下11位的复合操作:
⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾ → ⑹⑺⑻⑼⑽⑴⑵⑶⑷⑸⑾ → ⑹⑵⑶⑷⑸⑾⑺⑻⑼⑽⑴.
其结果是⑴,⑹,⑾位轮换为⑹,⑾,⑴,其它位都不变.
通过这种复合操作,总可以使这三位中的1排在2的前面.
通过不断的将每个Ai中的某相邻三位中的1移动到2的前面,最终可变为标准型.
因此答案21^5是正确的.