f*****k
发帖数: 353 | 1 A,B integer, uniformly distributed in [0, 1023], and A <= B, what's the
probability of (choosing A from B) is even?
我在那吭哧吭哧的算A!,B!,(B-A)!里面多少个2，算了15分钟，就被interviewer打断了，说
这也是一法，但是不是最简单的，大家说说怎么做吧 |
G*****u
发帖数: 1222 | 2 如果B是even number
Pr(A=even|B)=1/2
如果B是odd number
Pr(A=even|B)=1/2+1/2*1/B
Pr(A=even|B)=1/1024*[1/2*1024+1/2*(1/1+1/3+1/5+...+1/1023)]
=.502002 |
f*****k
发帖数: 353 | 3 Oh...
我没说清楚，(Choosing A from B)的意思是C(B,A),从B中选A的组合数，已经改过来了
【在 G*****u 的大作中提到】
: 如果B是even number
: Pr(A=even|B)=1/2
: 如果B是odd number
: Pr(A=even|B)=1/2+1/2*1/B
: Pr(A=even|B)=1/1024*[1/2*1024+1/2*(1/1+1/3+1/5+...+1/1023)]
: =.502002
|
s*******u
发帖数: 35 | 4 把A二进制展开
A=\sum_{i\in I}2^i
for some index set $I$
考虑多项式（1+x）^A over the field Z/2={0,1};
(1+x)^A=(1+x^(2^i))(i\in I) 的乘积. 所以一共有2^{#I} 项（#I 表示I中元素个
数）。 说明A选B(B<=A) 的组合数一共有 2^{#I} 个奇数。
所以奇数的概率是
1/1024\sum_{A=0}^{1023} 2^{#I(A)}/A;
偶数的概率用1减
了，说
【在 f*****k 的大作中提到】
: A,B integer, uniformly distributed in [0, 1023], and A <= B, what's the
: probability of (choosing A from B) is even?
: 我在那吭哧吭哧的算A!,B!,(B-A)!里面多少个2，算了15分钟，就被interviewer打断了，说
: 这也是一法，但是不是最简单的，大家说说怎么做吧
|
o****e
发帖数: 80 | 5 不明白，为什么
(1+x)^A=(1+x^(2^i))(i\in I) 的乘积. 所以一共有2^{#I} 项（#I 表示I中元素个 |
p*****k
发帖数: 318 | 6 finwalk, im not sure what exactly the interviewer had in mind,
but i will give you a hint:
http://en.wikipedia.org/wiki/Lucas%27_theorem
then consider the case when (B choose A) is odd, which results
a prob of (3/4)^10. so 1-(3/4)^10 being even.
seems to me salientxu's approach above is equivalent |
J*****n
发帖数: 4859 | 7
I am just curious what is your phd major on earth? Math education?
【在 p*****k 的大作中提到】
: finwalk, im not sure what exactly the interviewer had in mind,
: but i will give you a hint:
: http://en.wikipedia.org/wiki/Lucas%27_theorem
: then consider the case when (B choose A) is odd, which results
: a prob of (3/4)^10. so 1-(3/4)^10 being even.
: seems to me salientxu's approach above is equivalent
|
d*********n
发帖数: 27 | 8 (1+x)^(2^i) 的展开式中只有第一项和最后一项的系数为奇，因此别的项都可以扔掉（
证明方法：先考虑(1+x)^2, 展开为 1+2x+x^2, 2x 项可以扔掉，因为跟它有关的项系
数必定为偶；然后考虑(1+x)^4，如前所述它等价于(1+x^2)^2，展开后2x^2项又可以扔
掉；别的以此类推。）
这样一来，(1+x)^A 中系数有可能为奇的就只能来自 prod_{i\in I}(1+x^(2^i)); 展
开后是 2^(#I) 项
【在 o****e 的大作中提到】
: 不明白，为什么
: (1+x)^A=(1+x^(2^i))(i\in I) 的乘积. 所以一共有2^{#I} 项（#I 表示I中元素个
|
s****n
发帖数: 1237 | 9 me 2, pcasnik can always point the right theorem behind the problem.
really amazing
【在 J*****n 的大作中提到】
:
: I am just curious what is your phd major on earth? Math education?
|
s******n
发帖数: 785 | 10 帮看看这种思路对不对
a,b都整数，分布区间有2^10个连续整数，可以用二进制的方法排出0跟着10个1，而A，
B也可以用这些不同的1表示。条件限定A<=B，总共挑选方法有11*11/2种，而A
方法有11*10/2种，剩下的相等的概率就是1-10/11=1/11，不知道这样解对不对
了，说
【在 f*****k 的大作中提到】
: A,B integer, uniformly distributed in [0, 1023], and A <= B, what's the
: probability of (choosing A from B) is even?
: 我在那吭哧吭哧的算A!,B!,(B-A)!里面多少个2，算了15分钟，就被interviewer打断了，说
: 这也是一法，但是不是最简单的，大家说说怎么做吧
|
|
|
g**********1
发帖数: 1113 | 11 看懂题目，再来讨论问题。
【在 s******n 的大作中提到】
: 帮看看这种思路对不对
: a,b都整数，分布区间有2^10个连续整数，可以用二进制的方法排出0跟着10个1，而A，
: B也可以用这些不同的1表示。条件限定A<=B，总共挑选方法有11*11/2种，而A: 方法有11*10/2种，剩下的相等的概率就是1-10/11=1/11，不知道这样解对不对
:
: 了，说
|
s*********4
发帖数: 199 | 12 按杨辉三角写组合数
只有每行首尾，以及奇数行次首尾是奇数。 |
s***e
发帖数: 267 | 13 Very impressive. I am also curious, coach of IMO?
【在 J*****n 的大作中提到】
:
: I am just curious what is your phd major on earth? Math education?
|
s*****e
发帖数: 6 | 14 画杨辉三角形mod 2
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
前4行有f(4)=1个0，数第5-8行，可以分成3个三角形，左边和右边的正三角跟前4行是
一样的，中间一个倒三角有3+2+1=6个0，那么1-8行一共有f(8)=f(4)*3+(3+2+1)=1*3+6
=9个0。递推
f(16)=f(8)*3+(7+6+5+4+3+2+1),...,f(2^(n+1))=f(2^n)*3+(2^n)(2^n-1)/2
f(2^(n+1))/3^(n+1)=f(2^n)/3^n+((4/3)^n-(2/3)^n)/6
于是
f(1024)/3^10=f(1)/3+((4/3)^10-1)/(4/3-1)-(1-(2/3)^10)/(1-2/3))/6
=((4/3)^10+(2/3)^10-2)/2
f(1024)=(4^10+2^10-2*3^10)/2
概率就是再除以分母1024*1023/2 |
s********l
发帖数: 648 | 15 mark一下
了，说
【在 f*****k 的大作中提到】
: A,B integer, uniformly distributed in [0, 1023], and A <= B, what's the
: probability of (choosing A from B) is even?
: 我在那吭哧吭哧的算A!,B!,(B-A)!里面多少个2，算了15分钟，就被interviewer打断了，说
: 这也是一法，但是不是最简单的，大家说说怎么做吧
|
