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

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

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

  • 0

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

  • 0

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

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:


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

Link to comment
Share on other sites

  • 0

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

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

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.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...