flat assembler
Message board for the users of flat assembler.
Index
> Heap > Ponder This... 
Author 

bitRAKE
IBM Research has a puzzle each month...
The puzzle for December is: Quote: Consider a random walk on the 2d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i1, j), (i+1, j), (i, j1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five tetrominoes (considering mirror images to be the same). For each tetromino find the probability that it will be the one formed in this way. Code: __ lattice covered ____ (start in center) ______ ____ __  __ _  _ _ _    _ _ _ _ _  _ _   _ 

10 Dec 2008, 04:41 

nop
i luv puzzles but im not very gud at them is the answer 0.25^4 = .00390625 ? nah maybe not i know its 42 oops thats more than 1 i give up


10 Dec 2008, 10:35 

Tomasz Grysztar
bitRAKE wrote:
Is this right? Shouldn't it be Code: _
_


10 Dec 2008, 17:48 

edfed
in fact, there are only 2dominos
Code: __ lattice covered ____ (start in center) ______ ____ __  _ p = 2/3 _ _ p = 1/3 but there is a possibility, what appens if the point move from A top b and b to a continousously? _ 

10 Dec 2008, 19:30 

vid
Quote: Consider a random walk on the 2d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i1, j), (i+1, j), (i, j1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. Doesn't that mean you can walk infitely long without ever getting to solution? (as long as you don't say that random infinite times has to always produce all possible values... that goes more to philosophy IMO) 

10 Dec 2008, 20:47 

bitRAKE
Tomasz, your figure better represents the path  I shouldn't have closed the loop to represent the tetrominoes.
vid, sure, it can go to infinity without touching four unique points, but the probability of it doing so deminishes faster than all other options. I don't think the probabilities should sum to one. 

11 Dec 2008, 02:36 

r22
I would run a simulation using a good PRNG and see where the results converge. But I tend to take a bruteforce approach to mathematics where infinity is involved.
Using the ideal cases SQUARE: 1 * 1/2 * 1/4 = .125 LINE: 1 * 1/4 * 1/4 = .0625 L: 1 * 1/4 * 1/2 = .125 T: 1 * 1/2 * 1/4 * 1/4 = .03125 The T because it has to always double back has the worst P and LINE will have the 2nd worst. 

12 Dec 2008, 21:30 

Xorpd!
This seems quite straightforward to me.
Code: In the above, 1:4 are possible intermediate configurations (the asterisk marks the current active position) and A:E are the possible final outcomes. Now, P(A2) = ½P(A1), P(A1) = ¼+¼P(A2) = ¼+(1/8)P(A1) = 2/7 P(B2) = ½P(B1) P(B1) = ½+¼P(B2) = ½+(1/8)P(B1) = 4/7 P(C2) = ½+½P(C1) P(C1) = ¼P(C2) = (1/8)+(1/8)P(C1) = 1/7 P(B4) = ½P(B3) P(B3) = ¼+¼P(B4) = ¼+(1/8)P(B3) = 2/7 P(C4) = ½+½P(C3) P(C3) = ¼P(C4) = (1/8)+(1/8)P(C3) = 1/7 P(D4) = ½P(D3) P(D3) = ¼+¼P(D4) = ¼+(1/8)P(D3) = 2/7 P(E4) = ½P(E3) P(E3) = ¼+¼P(E4) = ¼+(1/8)P(E3) = 2/7 We know that P(1) = 1/3 P(3) = 2/3 So that P(A) = P(1)P(A1) = (1/3)(2/7) = 2/21 P(B) = P(1)P(B1)+P(3)P(B3) = (1/3)(4/7)+(2/3)(2/7) = 8/21 P(C) = P(1)P(C1)+P(3)P(C3) = (1/3)(1/7)+(2/3)(1/7) = 1/7 P(D) = P(3)P(D3) = (2/3)(2/7) = 4/21 P(E) = P(3)P(E3) = (2/3)(2/7) = 4/21 

13 Dec 2008, 08:24 

bitRAKE
Xorpd! wrote: This seems quite straightforward to me. Here is my brute force method: Code: lattice \ dd .W, .N, .E, .S .W dd .wW, .wN, .E, .wS .N dd .nW, .nN, .nE, .S .E dd .W, .eN, .eE, .eS .S dd .sW, .N, .sE, .sS .wW dd ._, .L, .wwE, .L .wN dd .Z, .L, .O, .wnS .wS dd .Z, .wsN, .O, .L .nW dd .L, .Z, .nwE, .O .nN dd .L, ._, .L, .nnS .nE dd .neW, .Z, .L, .O .eN dd .O, .L, .Z, .enS .eE dd .eeW, .L, ._, .L .eS dd .O, .esN, .Z, .L .sW dd .L, .O, .swE, .Z .sE dd .seW, .O, .L, .Z .sS dd .L, .ssN, .L, ._ .wwE dd .wW, .T, .eE, .T .wnS dd .T, .wN, .sE, .T .wsN dd .T, .T, .nE, .wS .neW = .wsN .nwE dd .nW, .T, .T, .eS .nnS dd .T, .nN, .T, .sS .eeW = .wwE .esN = .nwE .enS dd .sW, .eN, .T, .T .seW = .wnS .ssN = .nnS .swE = .enS ._ dd 0 .L dd 0 .T dd 0 .O dd 0 .Z dd 0 ... ; next node in random direction EAX mov edx,[edx+eax*4] cmp edx,lattice._ jc .loop add dword [edx],1 ; reset lattice lea edx,[lattice] jnc .loop ... 

15 Dec 2008, 08:10 

vid
xorpd: did you take into account probabilities of step sequences which go over and over same points? like moves to form "  " shape:
rightrigthtleftrightright rightleftrightrightleftrightright ... etc Shouldn't probability of these be added? And since there is infinite list of variations like these... sigh. I quess the originator of this puzzle didn't take it into account. 

15 Dec 2008, 11:03 

Tomasz Grysztar
bitRAKE wrote: I don't think the probabilities should sum to one. What the hell do you mean?! The probabilities MUST sum to one. Of course, since we are touching the infinity here, we are going to have some event that are possible, but still have 0 probability. It's like choosing random point from a plane. If you divide plane with a line into two parts, then probability of choosing a point in one of them is 1/2. But the probability of choosing precisely a (1,1) point, for example, is 0 (though it's still possible to get such outcome). Look also here. 

15 Dec 2008, 11:43 

bitRAKE
Tomasz Grysztar wrote:
That's why I never liked probability  now I wonder if it is possible to have infinite zero probabilities of events that can actually happen. My brute force program always did terminate, though. 

15 Dec 2008, 17:12 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.