SilentSpiral

数学游戏

洗牌

洗牌是这样一个过程： 先把一堆牌从正中间分成两堆，前一半是第一堆，后一半是第二堆。然后以第二堆的第一张，第一堆的第一张，第二堆的第二张，第一堆的第二张… …这样的顺序重排。52张牌洗牌几次可以回到最初的顺序？

1
2
3
4
5
6
7
8
9
10
a="abcdefghijklmnopqrstuvwxyz"
b=a+a.upper()
c=b
cnt=0
while(True):
	c="".join([i+j for i,j in zip(C[:26],c[26:])])
	cnt+=1
	if(c==b):
		break
print(cnt)

异或的期望

题目

从1,2,3，……98,99,2015这100个数中任意选择若干个数(可能为0)求异或，试求异或的期望值

根据期望的性质, \(E(X+Y)=E(X)+E(Y)\)
可以把这些数按位拆分, 逐位来处理期望值

1
2
3
4
>>> bin(2015)
'0b11111011111'
>>> 2015%128
95

注意到除了2015外, 每个数都小于128, 故可以单独处理高四位和低七位

1
2
3
4
5
6
7
8
>>> A=[i for i in range(1,100)]
>>> A.append(2015%128)
>>> b=["{:07b}".format(i) for i in A]
>>> c=[[i[-x] for i in b].count('1') for x in range(1,8)]
>>> [1,1,1,1]+c[::-1]
[1, 1, 1, 1, 37, 36, 49, 49, 49, 51, 51]
#其实可以丧心病狂的把这些写成一行....保证刺激,而且不会有zz跳出来指责我随意的变量名
#原本b=["%07b"%i for i in A], 但不知道为什么占位符%b不被识别, 迷

我们已经得到了这十一个二进制位上1的个数分别是
[1, 1, 1, 1, 37, 36, 49, 49, 49, 51, 51]

所以问题转化为100个元素里有k个元素a, 任取若干(可为0)元素其中元素a的个数为奇数的概率
\[\begin{align}P(不知道写啥) & = \cfrac{(C_{k}^{1}+C_{k}^{3}+C_{k}^{5}+C_{k}^{7}+...)2^{100-k}}{2^{100}}\\ &= \cfrac{(C_{k}^{1}+C_{k}^{3}+C_{k}^{5}+C_{k}^{7}+...)}{2^{k}}\\ &= \cfrac{2^{k}/2}{2^{k}}\\ &= \cfrac{1}{2}\end{align}\]

首先解释一下这个算式的意义, 分母为100个元素的全部子集的个数, 分子则是K个元素取到奇数的情况个数与其余100-k个元素的全部子集数的乘积, 这个弹夹和背包连在一起, 它就是一个平底锅, 我想大家是没有异议的

而后嘛, 带大家复习一下高中的知识了
\((C_{k}^{1}+C_{k}^{3}+C_{k}^{5}+C_{k}^{7}+...)=2^k/2\)
天理何在?
虽然我并不是很喜欢二项式定理来证明这个, 但无疑它是打出来说清楚比较方便的
\((a+b)^n=C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b^{1}+C_{n}^{2}a^{n-2}b^{2}+C_{n}^{3}a^{n-3}b^{3}+...\)
令a=1可以得到
\((1+x)^n=C_{n}^{0}+C_{n}^{1}x^{1}+C_{n}^{2}x^{2}+C_{n}^{3}x^{3}+...\)
再分别令x=1, x=-1得
\((1+1)^n=C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+C_{n}^{3}+C_{n}^{4}+C_{n}^{5}+C_{n}^{6}+C_{n}^{7}+...\)
\((1-1)^n=C_{n}^{0}-C_{n}^{1}+C_{n}^{2}-C_{n}^{3}+C_{n}^{4}-C_{n}^{5}+C_{n}^{6}-C_{n}^{7}+...\)
\((1+1)^n-(1-1)^n=2(C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+C_{n}^{7}+...)\)
\(C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+C_{n}^{7}+...=\cfrac{(1+1)^n-(1-1)^n}{2}=\cfrac{2^n}{2}\)
其实观察杨辉三角可以立得奇偶次项系数和一样多(都等于上一行系数和)
尝试了一下, 无论是画图还是用组合数恒等式, 都说不清, 果断弃疗

既然每一位上的异或结果为1的概率都是1/2
那么答案就理所当然的是(11111111111)2/2 = 2047/2 = 1023.5
　 　 　 　 　 　　……吗?

\(C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+C_{n}^{7}+...=\cfrac{(1+1)^n-(1-1)^n}{2}=\cfrac{2^n}{2}\)
第一个等号没问题
第二个等号问题很大
\(\cfrac{(1+1)^n-(1-1)^n}{2}=\cfrac{2^n}{2}\)
这一步其实默认了\((1-1)^{n}=0\)
\(0^{n}=0\)成立应当在n≥1时
当n0=时，\(0^{0}\)不存在
此时不能断定\(\cfrac{(1+1)^0-(1-1)^0}{2}=\cfrac{1}{2}\)

此时不妨换一个角度想, 0个元素中取到奇数个元素的情况裆燃是有0种可能

所以当k=0时取到奇数个a的概率为0, 否则概率为1/2

像之前那样求出来每一位上1的个数并非必要
such as [1, 1, 1, 1, 51, 51, 49, 49, 49, 36, 37]
只需要判断每一位上是否有1即可
譬如在此题目中把2015(11111011111)换成1887(11101011111)
最终答案就变成了1919/2=959.5 (快拿去坑害他人吧233333)

猜硬币

孙膑庞涓张仪都是鬼谷子的徒弟.一天鬼谷子出了这道题目: 鬼谷子抛一枚均匀的硬币三次，分别把三次的结果写在三个人额头上.每个人都可以看到别人头上的字但看不到自己头上的字.现在三个人同时猜自己头上的字.可以猜正，反，或者跳过.如果至少有一人猜对自己的字且无人猜错(猜跳过既不算对也不算错)，则集体获胜.如果三人都会采取最佳策略，且这一点本身也成为共识，那么获胜的概率是多少?

策略: 仅在看到另两人额头上字相同时, 猜与其相反的结果, 否则跳过.

这种策略获胜的概率是75%

真实情况 孙膑 庞涓 张仪 结果
000 猜错 猜错 猜错 失败
001 猜对 获胜
010 猜对 获胜
011 猜对 获胜
100 猜对 获胜
101 猜对 获胜
110 猜对 获胜
111 猜错 猜错 猜错 失败

可以看到每个人都有两次猜对两次猜错, 猜对猜错的总数都是6次
此种策略把猜错的可能性尽可能的集中到了两种具体的情况中去, 岂不美哉

但其实这个答案不是我想出来的, 而是写了个程序试出来了,恰好想到的第二个策略就碰上了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def method(B,C):
	if (B!=C):
		return 0
	if (B==C):
		return -B
    
def subJudge(x,y):
	if x==0:
		return None
	return x==y

def judge(A,B,C):
	if (A,B,C).count(False)>0:
		return False
	if (A,B,C).count(True)>0:
		return True
	return False

cnt=0
for A in (-1,1):
	for B in (-1,1):
		for C in (-1,1):
			a=subJudge(method(B,C),A)
			b=subJudge(method(A,C),B)
			c=subJudge(method(B,A),C)
			#print(a,b,c)
			if judge(a,b,c):
				cnt+=1
print(cnt)

构造递推

一个数只用 1,2,3,4这四种数字组成，而且相近的两位数永远相差1，比如1234321, 1212121等。 这样的n位数有多少个？

不妨把每一位上的数字分成两组, {1,4}和{2,3}
前一位是 {1,4}的情况下, 当前位可以是 {2,3}
前一位是 {2,3}的情况下, 当前位可以是 {1,2,3,4} = {1,4} + {2,3}
自左向右数第n位为{2,3}的数字的个数计为\(A_{n}\), 为{1,4}的个数计为\(B_{n}\)
易知\(A_{1}=B_{1}=2\)
我们所求的个数记作\(C_{n}=A_{n}+B_{n}\)
由之前的叙述可得递推关系:
\(A_{n+1}=A_{n}+B_{n}\)
\(B_{n+1}=A_{n}\)
故可以消去数列\(B_{n}\)有:
\(A_{0}=B_{1}=2\)
\(C_{n}=A_{n+1}=A_{n}+A_{n-1}\)

而后即是求解斐波那契数列了, 方法很多, 就不写了, 我比较喜欢矩阵快速幂的方法, 不涉及浮点数运算, 实优雅也

鸽巢原理

一个十进制的正整数完全由0和3组成，这个数可不可以是2018的倍数？

分析:
设此数为K, K|2018
2018=2*1009 (1009为素数)
则有K|1009, K|2
易知K的各位之和为3的倍数, K|3
只需要找到满足为1009的倍数的k=K/3
若此数非2的倍数, 乘10即可

解法1

费马小定理
a为任意整数, p为素数
\(a^{p}≡a \mod{p}\)
特殊的, 若gcd(a,p)=1
\(a^{p-1}≡1 \mod{p}\)

\(10^{1009-1}≡1 \mod{1009}\)
\(10^{1009-1}-1 ≡0\mod{1009}\)
\(K=\cfrac{10^{1009-1}-1}{3}\)
K的每一位都是3, 但K并不被2整除, 故10K即为我们要找的数字

解法2

构造数列1,11,111,1111……
易知其有无穷项
但其对1009取模只有有限项, 由鸽巢原理, 必有 am - an ≡ 0 mod 1009
am - an 必定为前m-n位为1, 后n位为0的形式, 所以一定是2的倍数
K = 3( am - an ), 即为所求

1
K=3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333330

十进制下只有253位, 相较费马小定理已经小了太多了

这种数列未考虑项中各位有0的情况, 但如果考虑的话, 又可能造成相减后未必仍符合要求的问题

解法3

\({k}\equiv{m} \mod{ 1009}\)

对于每一个m, 总能找到最小的kmin,
而后我们爆破a = int( bin(i)[2:] + str(kmin) ) , 寻找模1009余m的最小a
3(a-kmin)即为所求

在这里令m = 1
爆破得a = 100100011111111
K = 3(a-kmin) = 300300033333330 = 297621440370*1009

而100100011111111=int(bin(18686)[2:]+str(kmin))
可以爆破一下, 寻找更小的答案

1
2
3
4
5
for i in range(1,18687):
	r=int(bin(i)[2:])*3
	m=r%2018
	if m==0:
		print(r,i)

运行结果显示不存在更小的答案了

打赏