Guest Posted June 22, 2010 Report Share Posted June 22, 2010 given a n by 3 matrix of zeros and ones, what is the probability that you can trace a path of ones from a point on the left side to a point on the right side? (moving vertically or horizontally but not diagonally) example: n=3 0 1 1 1 1 0 0 1 0 answer in terms of n. Bonus: How about an n by m matrix? Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 (edited) Any kind of systematic approach seems difficult. So I have an idea. You can find a path of ones going from left to right if and only if there is no path of zeros going from top to bottom. For a 3x3 matrix, this must be 50% by symmetry. I'm still thinking for the rest. Edited June 22, 2010 by psychic_mind Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 (edited) given a n by 3 matrix of zeros and ones, what is the probability that you can trace a path of ones from a point on the left side to a point on the right side? (moving vertically or horizontally but not diagonally) example: n=3 0 1 1 1 1 0 0 1 0 answer in terms of n. Bonus: How about an n by m matrix? 68.75% Chance when n is 3 Edited June 22, 2010 by EE is the way to be Quote Link to comment Share on other sites More sharing options...

0 superprismatic Posted June 22, 2010 Report Share Posted June 22, 2010 You can find a path of ones going from left to right if and only if there is no path of zeros going from top to bottom. This isn't true. Here's a counterexample: 101 100 011 Here, there is no path of zeros going from top to bottom. But, there is also no path of ones going from left to right. Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 (edited) If its a 50/50 chance to be 1 or 0 than the odds that any one row of three random 1 in a row is .50^3 or .125. The chance of it not being the same number is 1-.50^3 or .875. In order to fail n times in a row, you first have to fail the first row at .875. If you go with two rows, you have a .875 chance of getting a .875 chance to fail. Etc... Represented by .875^N where N is the number of rows. The odds of finding a path would be the opposite of that, or winning , is 1-.875^N. Any single row chance to get all 1 is .50^M where M is the width. The chance to NOT get all 1 is 1-(.50^M). The odds of a matrix of N rows having no paths with all 1 would be 1-(1-.50^M)^N I haven't done math in forever, but I think the concept is right Edited June 22, 2010 by cbcarey Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 consider trying simpler examples. for example: n by 1. the probability is 1-2^{-n} Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 93.75% Chance when n=431.25 % Chance when n=2 68.75% Chance when n is 3 Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 In general, for an n x n matrix of 0's and 1's, there will be 2*(n**2) possible outcomes. Of these outcomes, n**2 of them fulfill the requirements of the puzzle path. This can be done for elaboration for a 2x2 matrix. The result set for the 3x3 matrix can also be shown through elaboration. The probability therefore for the general case is (n**2) / 2**(n**2). For n= 2, this is 4 / 16 = 25%. Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 22, 2010 Report Share Posted June 22, 2010 93.75% Chance when n=431.25 % Chance when n=2 Disregard Previous Posts. I now realize that I'm completely off base. Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 25, 2010 Report Share Posted June 25, 2010 for a matrix 1 by 1 there are 2^{n}^{2} combinations; 2^{1}^{2} or just 2, of matricies a '0' and no cross or a '1' and you can cross therefore: probability is 50% for a matrix 2 by 2 there are 2^{n}^{2} combinations; 2^{2}^{2} or just 2^{4} or 16 combinations in which 7 have the ability to cross therefore: 7/16 for a matrix 3 by 3 there are 2^{3}^{2} combinations; 2^{9} or 512 combinations in which 177 follow the rule therefore: 177/512 the first three are for sure the next seven are a guesstimation: for a 4x4 22177/65536 for a 5x5 9986179/33554432 for a 6x6 17986882088/69719476736 for a 7x7 129590277621748/562949953421312 for a 8x8 3.73E+018/1.84E+019 for a 9x9 4.31E+023/2.42E+024 for 10x10 1.99E+029/1.27E+030 anyways as n grows toward infinity the percent chance to cross gets closer and closer to zero which makes since because as you approach an infinity by infinity matrix the chance to cross infinity is obviously zero.... the percent change from one matrix to the next looks almost constant (unless I'm figuring this all wrong) and therefore it looks like a pattern is forming and it can be graphed and therefore it should have an equation: although that is alluding me right now Quote Link to comment Share on other sites More sharing options...

0 plainglazed Posted June 25, 2010 Report Share Posted June 25, 2010 not confident in the least but so far - 3((2^{N})^{2}-2^{N}+1/3)+4(3((2^{N-2})^{2}-2^{N-2}+1/3))8^{N} the left half of the sum in the numerator attempts to define the instances where you cross in a straight line. the difficulty is a zig zag traverse which is attempted to be accounted for in the right half of the sum in the numerator. probably not correct and it does not scale for when N is less than three where there cant be a ziz zag path to begin with. ughhh... Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 26, 2010 Report Share Posted June 26, 2010 heres a hint guys... the easiest method is to consider the number of arrangements of non-passable spaces that block all possible attempts to cross. that way you dont even have to worry about zig-zags. Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 26, 2010 Report Share Posted June 26, 2010 Well zig-zagging from left to right connecting 1's all the way from side to side doesn't seem any different then zig-zagging up and down connecting 0's all the way to prevent the 1's connecting from side to side unless I don't understand the clue or these matrices Quote Link to comment Share on other sites More sharing options...

0 plainglazed Posted June 28, 2010 Report Share Posted June 28, 2010 hey magician - just dawned on me as I reread your OP that I may have been going about this all wrong. Had been assuming you meant N columns which has me stymied. Do you mean three columns x N rows? Realize that typical nomenclature is rows x columns but also common is M rows and N columns. Quote Link to comment Share on other sites More sharing options...

0 superprismatic Posted June 28, 2010 Report Share Posted June 28, 2010 I wrote a program which computes all binary matrices for each pair of (rows,columns) in the following table. It then computes the number of these which have ledft-to-right paths of 1s as specified in the OP. I hope this helps those of you who are working on this problem. As for me, I don't see a good way to approach the problem analytically. rows columns # with paths # matrices possible % having a path 2 8 1393 65536 2.126% 3 8 571992 16777216 3.409% 2 7 577 16384 3.522% 3 7 116472 2097152 5.554% 2 6 239 4096 5.835% 3 6 23624 262144 9.012% 2 5 99 1024 9.668% 4 6 2089896 16777216 12.457% 3 5 4768 32768 14.551% 2 4 41 256 16.016% 4 5 204852 1048576 19.536% 3 4 956 4096 23.340% 5 5 8176228 33554432 24.367% 2 3 17 64 26.563% 4 4 19864 65536 30.310% 5 4 385064 1048576 36.723% 3 3 190 512 37.109% 6 4 7141192 16777216 42.565% 2 2 7 16 43.750% 4 3 1896 4096 46.289% 5 3 17744 32768 54.150% 3 2 37 64 57.813% 6 3 159552 262144 60.864% 7 3 1396608 2097152 66.595% 4 2 175 256 68.359% 8 3 11993600 16777216 71.487% 5 2 781 1024 76.270% 6 2 3367 4096 82.202% 7 2 14197 16384 86.652% 8 2 58975 65536 89.989% [/code] Quote Link to comment Share on other sites More sharing options...

0 Guest Posted June 30, 2010 Report Share Posted June 30, 2010 i guess it can be judged vertically by intersection of m and n,,n=1,1st col is checked,when n=2 and 3,2nd and 3rd cols are checked.so,min is 3,so,checked Quote Link to comment Share on other sites More sharing options...

## Question

## Guest

given a n by 3 matrix of zeros and ones, what is the probability that you can trace a path of ones from a point on the left side to a point on the right side? (moving vertically or horizontally but not diagonally)

example: n=3

0

111100 1 0

answer in terms of n.

Bonus: How about an n by m matrix?

## Link to comment

## Share on other sites

## 15 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.