p**e
发帖数: 41 | 1 1,mutilated chessboard variations
original:
If two opposing corners of a 8*8 chessboard are removed, can the
mutilated board be completely covered with 31 dominoes in such a way
that each domino covers 1*2 squares?
Variation 1:
Consider an 8x8 chessboard with one corner missing (so a total of 64-
1=63 squares). Can it be covered with 21 triominoes (dominoes that are
3*1 squares instead of the traditional 2*1)?
What if the triominoes are in an L shape instead of a line?
please give the proof as well.
2, High freq trading.
Assume you plan to do 1 millions times trades per day. Also assume for
each trade, you make 1$ with probability of 70% and lose 1$ with
probability of 30%. What is the expectation of your PNL E[pnl] per day?
If you set a stopping line, i.e., if the PNL hit -50K$, you stop the
trading system for today. What is the E[pnl|stopping line is -50K] with
this stopping strategy? Is this E[pnl] =, > or < the above E[pnl]? why? | D********n
发帖数: 978 | 2 第一道题。Original的用传统黑白相间染色，可以证明不可能。
用1x3的瓷砖也无法覆盖8x8去掉一个角。证明如下，把8x8放到坐标系第一象限，然去
掉的那个角处于原点的位置。8x8上面的每个格点的坐标为(i, j), i , j均为整数。给
每个方块上写上这个方块的左下角的格点的坐标之和。那么整个8x8去掉一个角上的所
有数字之和为448. 448 mod 3 = 1.
从另一方面看，1x3无论怎么摆，覆盖的数字之和模3必为0. 因此不可能覆盖。
如果用L型，则是可能的。画图很容易构造出覆盖方法。
domino
【在 p**e 的大作中提到】
: 1,mutilated chessboard variations
: original:
: If two opposing corners of a 8*8 chessboard are removed, can the
: mutilated board be completely covered with 31 dominoes in such a way
: that each domino covers 1*2 squares?
: Variation 1:
: Consider an 8x8 chessboard with one corner missing (so a total of 64-
: 1=63 squares). Can it be covered with 21 triominoes (dominoes that are
: 3*1 squares instead of the traditional 2*1)?
: What if the triominoes are in an L shape instead of a line?
| p**e
发帖数: 41 | 3 你这个构造左下角的格点的坐标之和代表小格的思路太巧妙了！ ZAN!
我onsite的时候还在苦苦思考用黑白颜色的老方法去解1*3的brick的问题。
【在 D********n 的大作中提到】
: 第一道题。Original的用传统黑白相间染色，可以证明不可能。
: 用1x3的瓷砖也无法覆盖8x8去掉一个角。证明如下，把8x8放到坐标系第一象限，然去
: 掉的那个角处于原点的位置。8x8上面的每个格点的坐标为(i, j), i , j均为整数。给
: 每个方块上写上这个方块的左下角的格点的坐标之和。那么整个8x8去掉一个角上的所
: 有数字之和为448. 448 mod 3 = 1.
: 从另一方面看，1x3无论怎么摆，覆盖的数字之和模3必为0. 因此不可能覆盖。
: 如果用L型，则是可能的。画图很容易构造出覆盖方法。
:
: domino
| y****n
发帖数: 60 | 4 第二题要具体算出来吗？
很容易argue E(stop at -50K) < E(no stop) 因为接着玩期望值是赚钱。
【在 p**e 的大作中提到】
: 1,mutilated chessboard variations
: original:
: If two opposing corners of a 8*8 chessboard are removed, can the
: mutilated board be completely covered with 31 dominoes in such a way
: that each domino covers 1*2 squares?
: Variation 1:
: Consider an 8x8 chessboard with one corner missing (so a total of 64-
: 1=63 squares). Can it be covered with 21 triominoes (dominoes that are
: 3*1 squares instead of the traditional 2*1)?
: What if the triominoes are in an L shape instead of a line?
| p**e
发帖数: 41 | 5 我当时是这么做的： 但是面试官好像不是很满意：
Consider a random walk, starting from point 0, go +1 step with probability
0.7, and go -1 step with probability 0.3.
It is easy to calculate that the Prob(0 --> -1) = 3/7.
therefore the Prob(0 --> -50000) = (3/7)^(50000) almost equal to 0.
So the E[pnl|set the stopping line -50K $] almost equal to the original E[
pnl], but a lit bit less.
那个面试官似乎不置可否， 所以我也不知道我的答案正确不正确。所以贴出来大家帮
忙看看
【在 y****n 的大作中提到】
: 第二题要具体算出来吗？
: 很容易argue E(stop at -50K) < E(no stop) 因为接着玩期望值是赚钱。
| w*******x
发帖数: 489 | 6 The argument of the probability is totally wrong.
Though I also don't know how to calculate the Expectation value exactly with
stopping condition
probability
【在 p**e 的大作中提到】
: 我当时是这么做的： 但是面试官好像不是很满意：
: Consider a random walk, starting from point 0, go +1 step with probability
: 0.7, and go -1 step with probability 0.3.
: It is easy to calculate that the Prob(0 --> -1) = 3/7.
: therefore the Prob(0 --> -50000) = (3/7)^(50000) almost equal to 0.
: So the E[pnl|set the stopping line -50K $] almost equal to the original E[
: pnl], but a lit bit less.
: 那个面试官似乎不置可否， 所以我也不知道我的答案正确不正确。所以贴出来大家帮
: 忙看看
| p********6
发帖数: 1802 | 7 最后放你过了没？
probability
【在 p**e 的大作中提到】
: 我当时是这么做的： 但是面试官好像不是很满意：
: Consider a random walk, starting from point 0, go +1 step with probability
: 0.7, and go -1 step with probability 0.3.
: It is easy to calculate that the Prob(0 --> -1) = 3/7.
: therefore the Prob(0 --> -50000) = (3/7)^(50000) almost equal to 0.
: So the E[pnl|set the stopping line -50K $] almost equal to the original E[
: pnl], but a lit bit less.
: 那个面试官似乎不置可否， 所以我也不知道我的答案正确不正确。所以贴出来大家帮
: 忙看看
| i****k
发帖数: 668 | 8 你不会涂三个颜色么...
【在 p**e 的大作中提到】
: 你这个构造左下角的格点的坐标之和代表小格的思路太巧妙了！ ZAN!
: 我onsite的时候还在苦苦思考用黑白颜色的老方法去解1*3的brick的问题。
| p**e
发帖数: 41 | 9 我真的不会三个颜色的方法。
你给我讲一下吧
【在 i****k 的大作中提到】
: 你不会涂三个颜色么...
| p**e
发帖数: 41 | 10 估计肯定没戏。 我回答的也不好，而且feeling也比较差。
【在 p********6 的大作中提到】
: 最后放你过了没？
:
: probability
| | | D********n
发帖数: 978 | 11 我不喜欢涂色;). 不过涂色也是可以的。图3种{1,2,3}从左上角的开始
图。
1, 2, 3, 1, 2, 3, 1, 2
2, 3, 1, 2, 3, 1, 2, 3
3, 1, 2, 3, 1, 2, 3, 1
...
这样图下来一共是21个1, 22个2, 21个3.
如果我们去掉左上角的那个1，则是20个1, 22个2, 21个3, 因此不能完全覆盖。
注意：去掉哪个角对于覆盖来讲其实没关系，因为可以旋转。但是，对于这个染色来讲
，如果你去掉左下角的就不方便证明了。
【在 p**e 的大作中提到】
: 我真的不会三个颜色的方法。
: 你给我讲一下吧
| x******a
发帖数: 6336 | 12 this one works for the 'L' shape as well if I understand 'L' consists of 3
cubes.
【在 D********n 的大作中提到】
: 我不喜欢涂色;). 不过涂色也是可以的。图3种{1,2,3}从左上角的开始
: 图。
: 1, 2, 3, 1, 2, 3, 1, 2
: 2, 3, 1, 2, 3, 1, 2, 3
: 3, 1, 2, 3, 1, 2, 3, 1
: ...
: 这样图下来一共是21个1, 22个2, 21个3.
: 如果我们去掉左上角的那个1，则是20个1, 22个2, 21个3, 因此不能完全覆盖。
: 注意：去掉哪个角对于覆盖来讲其实没关系，因为可以旋转。但是，对于这个染色来讲
: ，如果你去掉左下角的就不方便证明了。
| D********n
发帖数: 978 | 13 3x1的长方形，无论怎么摆都会有3种颜色，每种各1个。L型的也是这样么？
【在 x******a 的大作中提到】
: this one works for the 'L' shape as well if I understand 'L' consists of 3
: cubes.
| y**b
发帖数: 73 | 14 实在想不通你的3/7是怎么出来的？
这个问题是一个经典的Gambler's ruin problem, 你google一下有一堆答案。基本想法
是把它看作一个Brownian motion with drift，计算1m步以内撞到boundary（－50K）
的概率，然后expected value就好算了。
probability
【在 p**e 的大作中提到】
: 我当时是这么做的： 但是面试官好像不是很满意：
: Consider a random walk, starting from point 0, go +1 step with probability
: 0.7, and go -1 step with probability 0.3.
: It is easy to calculate that the Prob(0 --> -1) = 3/7.
: therefore the Prob(0 --> -50000) = (3/7)^(50000) almost equal to 0.
: So the E[pnl|set the stopping line -50K $] almost equal to the original E[
: pnl], but a lit bit less.
: 那个面试官似乎不置可否， 所以我也不知道我的答案正确不正确。所以贴出来大家帮
: 忙看看
| x******a
发帖数: 6336 | 15 from your graph, i see yes.
【在 D********n 的大作中提到】
: 3x1的长方形，无论怎么摆都会有3种颜色，每种各1个。L型的也是这样么？
| D********n
发帖数: 978 | 16 您的意思是L形只能当成L形用，不能旋转成"厂"或者"J"的形状？如果是这样的话，答
案是否定的，一群L字之间必然是有空隙的。当然无法填满8x8 - 1. 甚至，别说8x8-1了，连2x3也
无法填满。
如果你画个图用L形填满8x8-1的话，你需要旋转它. 这就是为什么俄罗斯方块游戏有个按键让你旋
转。
【在 x******a 的大作中提到】
: from your graph, i see yes.
| p**e
发帖数: 41 | 17 I use this method:
A random walk, starting from 0, will walk +1 steps with probability p, and -
1 steps with probabolity 1-p, then the
Prob[hitting 0] = 2 min(p,1-p)
Prob[hitting -1]= (1-p)/p
Prob[hitting -k]= ( (1-p)/p )^k
here we have p = 0.7, that is why I calc the 3/7
我也不太清楚我到底错在哪里， 请大家帮忙讨论一下
【在 y**b 的大作中提到】
: 实在想不通你的3/7是怎么出来的？
: 这个问题是一个经典的Gambler's ruin problem, 你google一下有一堆答案。基本想法
: 是把它看作一个Brownian motion with drift，计算1m步以内撞到boundary（－50K）
: 的概率，然后expected value就好算了。
:
: probability
| p**e
发帖数: 41 | 18 我看一下，还是没完全懂，
1， 如果我去掉右上角的2，岂不是变成21个1, 21个2, 21个3，你怎么证明不可以？
2， 你是按照什么顺序来涂色的？ 从左上开始向右，到board再转下一行的最左边，
然后依次继续，还是别的什么顺序？ 这种涂色唯一哪？ （假设每种颜色等价，我只
是问涂色策略唯一吗？）
谢谢
【在 D********n 的大作中提到】
: 我不喜欢涂色;). 不过涂色也是可以的。图3种{1,2,3}从左上角的开始
: 图。
: 1, 2, 3, 1, 2, 3, 1, 2
: 2, 3, 1, 2, 3, 1, 2, 3
: 3, 1, 2, 3, 1, 2, 3, 1
: ...
: 这样图下来一共是21个1, 22个2, 21个3.
: 如果我们去掉左上角的那个1，则是20个1, 22个2, 21个3, 因此不能完全覆盖。
: 注意：去掉哪个角对于覆盖来讲其实没关系，因为可以旋转。但是，对于这个染色来讲
: ，如果你去掉左下角的就不方便证明了。
| l*****y
发帖数: 56 | 19 算出了撞到ｂｏｕｎｄａｒｙ的概率之后，又如何计算总收益的ｅｘｐｅｃｔａｔｉｏ
ｎ呢？
最后收益会有很多可能性，要算每种結果的可能性吗？
请指教！
【在 y**b 的大作中提到】
: 实在想不通你的3/7是怎么出来的？
: 这个问题是一个经典的Gambler's ruin problem, 你google一下有一堆答案。基本想法
: 是把它看作一个Brownian motion with drift，计算1m步以内撞到boundary（－50K）
: 的概率，然后expected value就好算了。
:
: probability
| z****t
发帖数: 78 | 20 Are you sure about this? I do not Gambler's ruin problem. But all variances
I can find on-line allow infinite number of plays as long as the player does
not lose. This problem sounds more like a knock-out option to me.
【在 y**b 的大作中提到】
: 实在想不通你的3/7是怎么出来的？
: 这个问题是一个经典的Gambler's ruin problem, 你google一下有一堆答案。基本想法
: 是把它看作一个Brownian motion with drift，计算1m步以内撞到boundary（－50K）
: 的概率，然后expected value就好算了。
:
: probability
| | | l*****y
发帖数: 56 | 21 同意楼主，感觉knock-out option更合理， 用binomial tree + dynamic programming
应该能算出来，但是看到１ ｍｉｌｌｉｏｎ我就不太确定了，有更好的办法算吗？
variances
does
【在 z****t 的大作中提到】
: Are you sure about this? I do not Gambler's ruin problem. But all variances
: I can find on-line allow infinite number of plays as long as the player does
: not lose. This problem sounds more like a knock-out option to me.
| s******k
发帖数: 3716 | 22 每行涂一个颜色，
R,R,R,R....
G,G,G,G...
B,B,B,B...
初始化的时候红色23个，绿色24个，蓝色16个。
一块板要么覆盖三个不同颜色，要么覆盖同一颜色三个，所以
它们之间的差被三除余数总是不变。
【在 D********n 的大作中提到】
: 我不喜欢涂色;). 不过涂色也是可以的。图3种{1,2,3}从左上角的开始
: 图。
: 1, 2, 3, 1, 2, 3, 1, 2
: 2, 3, 1, 2, 3, 1, 2, 3
: 3, 1, 2, 3, 1, 2, 3, 1
: ...
: 这样图下来一共是21个1, 22个2, 21个3.
: 如果我们去掉左上角的那个1，则是20个1, 22个2, 21个3, 因此不能完全覆盖。
: 注意：去掉哪个角对于覆盖来讲其实没关系，因为可以旋转。但是，对于这个染色来讲
: ，如果你去掉左下角的就不方便证明了。
| c**********s
发帖数: 295 | 23 numerical: typical tree.
analytical: change of measure + reflection |
|
