[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 1 1

1 1 0

0 1 0

answer in terms of n.

Bonus: How about an n by m matrix?

[Guest]

  Reveal hidden contents

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

[Guest]

  On 6/22/2010 at 3:10 PM, magician said:

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?

  Reveal hidden contents

68.75% Chance when n is 3

Edited June 22, 2010 by EE is the way to be

[superprismatic]

  On 6/22/2010 at 5:58 PM, psychic_mind said:

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.

[Guest]

  Reveal hidden contents

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.

  Reveal hidden contents

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

[Guest]

consider trying simpler examples. for example: n by 1. the probability is 1-2^-n

[Guest]

  Reveal hidden contents

93.75% Chance when n=4

  Reveal hidden contents

31.25 % Chance when n=2

  On 6/22/2010 at 6:58 PM, EE is the way to be said:

  Reveal hidden contents

68.75% Chance when n is 3

[Guest]

  Reveal hidden contents

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%.

[Guest]

  On 6/22/2010 at 7:52 PM, EE is the way to be said:

  Reveal hidden contents

93.75% Chance when n=4

  Reveal hidden contents

31.25 % Chance when n=2

Disregard Previous Posts. I now realize that I'm completely off base.

[Guest]

  Reveal hidden contents

for a matrix 1 by 1 there are 2ⁿ² combinations; 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ⁿ² combinations; 2²² or just 2⁴ or 16 combinations in which 7 have the ability to cross therefore: 7/16

for a matrix 3 by 3 there are 2³² combinations; 2⁹ 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

[plainglazed]

  Reveal hidden contents

not confident in the least but so far -

3((2^N)²-2^N+1/3)+4(3((2^N-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...

[Guest]

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.

[Guest]

  Reveal hidden contents

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

[plainglazed]

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.

[superprismatic]

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]

[Guest]

  Reveal hidden contents

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