w******t 发帖数: 13 | 1 Given N lightbulbs and N buttons, such that:
a.Each button toggles 1<=k
b.If button i toggles bulb j, then button j toggles bulb i
What additional conditions, if any, are required to guarantee that we can
turn all the bulbs on given any initial state. Describe how to light all the
lightbulbs under sufficient conditions given an initial state. | p**********9 发帖数: 101 | 2 借这个title也贴两个刚面的面试题
1. A gift show, there is car behind one of the three doors,say A,B, C. Now
You choose a door say A, then the host open another one of rest doors say C
which is empty. Now in order to get the car, should you switch or not switch
the doors from A to B. Why?
2. Integration Problem
How to integrate normal funtion and prove it's Cumulative density function
is from 0 to 1. | J******d 发帖数: 506 | 3 不理解第二题。
C
switch
【在 p**********9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 借这个title也贴两个刚面的面试题 : 1. A gift show, there is car behind one of the three doors,say A,B, C. Now : You choose a door say A, then the host open another one of rest doors say C : which is empty. Now in order to get the car, should you switch or not switch : the doors from A to B. Why? : 2. Integration Problem : How to integrate normal funtion and prove it's Cumulative density function : is from 0 to 1.
| p**********9 发帖数: 101 | 4 就是对normal distribution积分,怎么能得证明累积分布是从0到1的 | z****i 发帖数: 406 | 5 还是不理解。。。
对normal distribution的CDF积分? it's not bounded above by 1...
如果是对pdf积分, 那积出来不就是1吗?如果不是整个实数空间上积分,那就是小于1啊
【在 p**********9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是对normal distribution积分,怎么能得证明累积分布是从0到1的
| J******d 发帖数: 506 | 6 啊?啥叫对normal dist积分?你是说对PDF积分?证明PDF的积分=CDF?
这不是显然的么?
【在 p**********9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是对normal distribution积分,怎么能得证明累积分布是从0到1的
| k*******d 发帖数: 1340 | 7 我觉得你说的就是这个题目的答案吧,证明了CDF在0和1之间
突然想到一个stupid question,如何证明对normal pdf从负无穷到正无穷的积分是1呢
?那个积分硬算不大好算啊,CDF没有closed form表示吧
也许这也是题目想问的
于1啊
【在 z****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是不理解。。。 : 对normal distribution的CDF积分? it's not bounded above by 1... : 如果是对pdf积分, 那积出来不就是1吗?如果不是整个实数空间上积分,那就是小于1啊
| z****i 发帖数: 406 | 8 把两个这样的CDF乘起来,把其中一个的自变量从x换成y,写成一个二重积分,然后换
成极坐标做。
【在 k*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得你说的就是这个题目的答案吧,证明了CDF在0和1之间 : 突然想到一个stupid question,如何证明对normal pdf从负无穷到正无穷的积分是1呢 : ?那个积分硬算不大好算啊,CDF没有closed form表示吧 : 也许这也是题目想问的 : : 于1啊
| k*******d 发帖数: 1340 | 9 very nice!
太猛了!
谢谢~
【在 z****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把两个这样的CDF乘起来,把其中一个的自变量从x换成y,写成一个二重积分,然后换 : 成极坐标做。
| p**********9 发帖数: 101 | 10 这应该是正解,sorry没讲清楚,就是证明正无穷到负无穷的积分是1.但我也忘了吧x换
成什么了。
谁能讲讲第一道题Monty Hall problem
为什么换是2/3,不换是1/3
看了答案还是不理解
【在 z****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把两个这样的CDF乘起来,把其中一个的自变量从x换成y,写成一个二重积分,然后换 : 成极坐标做。
| | | z****i 发帖数: 406 | 11 如果不换,whatever the host did is irrelevant, you win if and only if the
gift is behind door A, and the probability if 1/3.
如果换, you win if and only if there is no gift behind door C, and the prob
is 2/3.
【在 p**********9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这应该是正解,sorry没讲清楚,就是证明正无穷到负无穷的积分是1.但我也忘了吧x换 : 成什么了。 : 谁能讲讲第一道题Monty Hall problem : 为什么换是2/3,不换是1/3 : 看了答案还是不理解
| z****g 发帖数: 1978 | 12 很多方法可以做
1. 做变换
2. 在复平面积分,用Residual value theory
3. 对积分构造ODE,解一个齐次ODE
【在 k*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : very nice! : 太猛了! : 谢谢~
| c*****w 发帖数: 50 | 13 I think it is k|N by Lagrange theorem
the
【在 w******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given N lightbulbs and N buttons, such that: : a.Each button toggles 1<=k: b.If button i toggles bulb j, then button j toggles bulb i : What additional conditions, if any, are required to guarantee that we can : turn all the bulbs on given any initial state. Describe how to light all the : lightbulbs under sufficient conditions given an initial state.
| k*******d 发帖数: 1340 | 14 唉,我不是math major的啊
zhucai的解法是非数学专业的也好懂的
【在 z****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很多方法可以做 : 1. 做变换 : 2. 在复平面积分,用Residual value theory : 3. 对积分构造ODE,解一个齐次ODE
| b********a 发帖数: 5418 | 15 没人回这个题?
can
the
【在 w******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given N lightbulbs and N buttons, such that: : a.Each button toggles 1<=k: b.If button i toggles bulb j, then button j toggles bulb i : What additional conditions, if any, are required to guarantee that we can : turn all the bulbs on given any initial state. Describe how to light all the : lightbulbs under sufficient conditions given an initial state.
| c**z 发帖数: 66 | 16 i still don't understand question 1 | z****g 发帖数: 1978 | 17 I thought it is clear.
Define each button_i's behavior as
X_i = ( X_{i, 1}, X_{i, 2}, .....X_{i, K})^t
where i = 1..K and X_{i,j} = 1 if button i toggles bulb j and 0 if not.
So
X = (X_1, X_2, ..., X_K) defines a operator matrix.
Notice the sequence of pushing buttons is interchangeable, define
n = ( n_1, n2, ... n_K)^t where n_i is number of times button i got
pressed.
The question is equivalent to there exists a n such that
X*n mod 2 = 1.
Since X is symmetric
X*n = X^t*n => X_i^t * n mod 2 = 1
【在 b********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没人回这个题? : : can : the
| n****e 发帖数: 629 | 18 1.对称矩阵这个表示很好
2.这个解没有解决问题。原题是问,在任意情况下都可以达到全开。
比如三盏灯,X={{1,1,1},{1,1,1},{1,1,1}},很显然不行
【在 z****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I thought it is clear. : Define each button_i's behavior as : X_i = ( X_{i, 1}, X_{i, 2}, .....X_{i, K})^t : where i = 1..K and X_{i,j} = 1 if button i toggles bulb j and 0 if not. : So : X = (X_1, X_2, ..., X_K) defines a operator matrix. : Notice the sequence of pushing buttons is interchangeable, define : n = ( n_1, n2, ... n_K)^t where n_i is number of times button i got : pressed. : The question is equivalent to there exists a n such that
| z****g 发帖数: 1978 | 19 OK, in that case, it's another story.
My intuition is that it has something to do with the finite symmetric
group.
Define the state of bulbs as vector ( b_1, b_2, ..., b_K ) where b_1 = 1
means on and 0 means off. And the operator + :
1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
then
All possible states of bulbs and operator + {B, + } formulate a finite
symmetric group. where all bulbs are off (0,0,...0) are the zero
element, and all buttons can be defined as one element within the group.
So the ques
【在 n****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1.对称矩阵这个表示很好 : 2.这个解没有解决问题。原题是问,在任意情况下都可以达到全开。 : 比如三盏灯,X={{1,1,1},{1,1,1},{1,1,1}},很显然不行
| p*****k 发帖数: 318 | 20
this seems to be necessary but not sufficient.
e.g., if N=4, k=2, one could have (in ziqing's notation):
1100
1100
0011
0011
plz feel free to chime in - my guess is to rule out
all the cases that i-th switch toggles i-th bulb
when k>1
【在 c*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think it is k|N by Lagrange theorem : : the
| b********a 发帖数: 5418 | 21 看你链接里面的图片让我想到了魔方。
【在 p*****k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : this seems to be necessary but not sufficient. : e.g., if N=4, k=2, one could have (in ziqing's notation): : 1100 : 1100 : 0011 : 0011 : plz feel free to chime in - my guess is to rule out : all the cases that i-th switch toggles i-th bulb : when k>1
| c*****w 发帖数: 50 | 22 En... Thanks for your post. My answer is wrong.
Following ziqing's notation, the operator matrix needs to be invertible, i.e. the rows should be independent. But the rows (or cols) of the matrix sum up to mod((k,k,...,k),2), so a necessary condition seems to be k is odd.
【在 p*****k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : this seems to be necessary but not sufficient. : e.g., if N=4, k=2, one could have (in ziqing's notation): : 1100 : 1100 : 0011 : 0011 : plz feel free to chime in - my guess is to rule out : all the cases that i-th switch toggles i-th bulb : when k>1
|
|