Jump to content
BrainDen.com - Brain Teasers
  • 0


Guest
 Share

Question

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?

Link to comment
Share on other sites

15 answers to this question

Recommended Posts

  • 0

  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 by psychic_mind
Link to comment
Share on other sites

  • 0
  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 by EE is the way to be
Link to comment
Share on other sites

  • 0
  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.

Link to comment
Share on other sites

  • 0

  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 by cbcarey
Link to comment
Share on other sites

  • 0

  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

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0
  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.

Link to comment
Share on other sites

  • 0

  Reveal hidden contents

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

for a matrix 3 by 3 there are 232 combinations; 29 or 512 combinations in which 177 follow the rule therefore: 177/512

the first three are for sure

the next seven are a guesstimation:

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

Link to comment
Share on other sites

  • 0

  Reveal hidden contents

not confident in the least but so far -

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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

  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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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]

Link to comment
Share on other sites

  • 0

  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

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...