[superprismatic]

Consider a 100-long array of numbers

containing 10 of each of the numbers

1,2,3,4,5,6,7,8,9,10 in random order.

As an example, consider the array

  3  3  1  7  1  5  8 10  4  7

 10  3  1  6  9  3  9  8  1  4

  9  5  1  1  7  5  5  5  2  9

  2  8  1  3  7  5  7  8 10  6

 10  9  6  9  3  1  8  9 10  7

  2  2  1  8  5  1  4  7  4  6

  4  8 10  4  6  8  7  6  4  5

  5  3 10  4  7  6  6 10  2  2

  2  9  2 10  7  9 10  2  3  4

  8  3  6  3  9  8  6  4  2  5

[/code]

Consider the following:  First,

choose an element in a random

position from the first 10 elements

of the array.  That number will

determine how far to advance in the

array to get the next number.  This

continues until one gets to a number

such that one cannot advance by that

amount and still stay inside the

array.  The final number together

with its position in the array is

our result.


For example, suppose one were to

start with the number in the 7[sup]th[/sup]

position.  This number is an 8.  So

we move eight positions to a 9.  From

there, we move nine positions to a 1,

then to a 7, then 8,6,1,8,5,6,8,4,10,

2,4,3, and finally to a 6 in position

97. Thus, the pair (6,97) is our

result.


If a random array such as is described

in the first sentence of this puzzle

were presented to two people, and each

were to pick a random starting position

in the first 10 positions, what is the

probability that they would both end

end up with identical results after

completing the process described above?

Identical results would mean that each

would arrive at the same number in the

same position in the array.

[Guest]

Umm..is this a real riddle or just all the hardest questions out of a math book bundeled together? what's the point of solving this?

I'd say there's 1/45 chance to stop at position 90 (cause that's only if it has 10) 2/45 chance to stop at position 91 (cause it has to be either 10 or 9)..........10/45 chance to stop at position 100 (cause all the numbers would work there) though that is disregarding everything else prehand, I don't see any other way to solve it than to write a program to try every possible situation...

Anyways, if above calculation is true, then I'd say that the chance of two people landing in the same position would be (1²+2²+3²+...+10²)/45²

(that's pretty much also the chance I'm correct in this answer)

[Wilson]

Don't laugh, I'm none too sharp at maths...

They are both going to finish on the last line.

Both have 1/10 chance of landing on a particular position.

1/100 chance of landing on the same?

OR

First guy lands wherever on last line.

1/10 chance that 2nd guy lands on same?

[superprismatic]

Don't laugh, I'm none too sharp at maths...

They are both going to finish on the last line.

Both have 1/10 chance of landing on a particular position.

1/100 chance of landing on the same?

OR

First guy lands wherever on last line.

1/10 chance that 2nd guy lands on same?

You may want to try making up such an array. It's

pretty easy to to -- just scatter ten 10s in a blank array,

then, scatter in ten 9's, etc. until you're done.

Then pick a few starting points and go through the

process to see what kinds of things are happening.

Watch how two or more such paths interact. That

might give you some ideas.

[Guest]

That's just weird.

[plainglazed]

seems to me the average move/advance would be five so 20 moves on average per game? odds of not landing on the other players number 9/10 per move? odds of not landing on the other players number per game (9/10)²⁰? odds of each ending on the same number just less than 88%? probably way over simplified and already see lots of probable holes here but ...

Seems a likely candidate for a programming trial. Fun to ponder. Will keep thinking.

Edited April 12, 2010 by plainglazed

[Guest]

...Watch how two or more such paths interact...

I think I've got something:

If two people land on the same spot (not necessarily the last ones) they'll continue on the same path! for example if both people cross path and land on position 29 for example they will continue on the same path and end up together in the same position...

So they chances of them NOT ending up in the same square is the chance that they do not cross paths at all at any given square, if only it weren't a randomized array then I would've solved it by now, but there's gotta be a mathematical explanation from here...

There could be a pattern in the array that goes like this: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, x, and if it existed in the square anyone who comes across it will certainly land on x and continue on from there, if such path existed the chances of two people landing in the same last square it 100%

Edited April 13, 2010 by qwe qwe

[Guest]

qwe qwe is on the right track. If you ever cross paths, you will end on the same place.

On average, it will take 20 "moves" to get to the end of the array (100 / an average move of 5).

At any time along your path, you will be no more than 10 spaces away from the "target" path. So for any move, you have a 1 in 10 chance of meeting up with the target path. (you also had a 1 in 10 chance of starting out on the same space).

Given this, the chances are very high (Have not worked out exactly what the chances are yet)

[Guest]

I FOUND SOMETHING!

I wrote a script in Flash that'll randomize an array just like in the riddle and test out all the starting points where they lead, here's what I got for 3 tries:

Try #1

Matrix:

1 2 1 6 2 2 7 9 3 3

2 1 6 2 2 7 9 3 3 8

1 6 2 2 7 9 3 3 8 10

6 2 2 7 9 3 3 8 10 10

2 2 7 9 3 3 8 10 10 4

2 7 9 3 3 8 10 10 4 3

7 9 3 3 8 10 10 4 3 9

9 3 3 8 10 10 4 3 9 2

3 3 8 10 10 4 3 9 2 6

3 8 10 10 4 3 9 2 6 8

Pairs:

(1,99)

(2,99)

(3,99)

(4,99)

(5,99)

(6,99)

(7,99)

(8,99)

(9,99)

(10,99)

Try #2

Matrix:

10 6 3 9 9 4 4 5 2 9

6 3 9 9 4 4 5 2 9 6

3 9 9 4 4 5 2 9 6 10

9 9 4 4 5 2 9 6 10 9

9 4 4 5 2 9 6 10 9 5

4 4 5 2 9 6 10 9 5 7

4 5 2 9 6 10 9 5 7 8

5 2 9 6 10 9 5 7 8 5

2 9 6 10 9 5 7 8 5 3

9 6 10 9 5 7 8 5 3 3

Pairs:

(1,94)

(2,94)

(3,94)

(4,94)

(5,94)

(6,94)

(7,94)

(8,94)

(9,94)

(10,94)

Try #3

Matrix:

3 5 2 2 1 1 6 4 1 5

5 2 2 1 1 6 4 1 5 5

2 2 1 1 6 4 1 5 5 4

2 1 1 6 4 1 5 5 4 4

1 1 6 4 1 5 5 4 4 3

1 6 4 1 5 5 4 4 3 3

6 4 1 5 5 4 4 3 3 8

4 1 5 5 4 4 3 3 8 6

1 5 5 4 4 3 3 8 6 1

5 5 4 4 3 3 8 6 1 8

Pairs:

(1,97)

(2,97)

(3,97)

(4,97)

(5,97)

(6,97)

(7,97)

(8,97)

(9,97)

(10,97)

I'm going to check the code again to see if it's really working properly but I think that's kinda the answer, I had a feeling that no matter how you arrange the array ALL paths are gonna cross at some point, though I have no mathematical way to prove it...(yet =P)

Edited April 13, 2010 by qwe qwe

[Guest]

roughly, it would be 1- (9/10)^20 = 88%

[Guest]

Man do I love ActionScript: http://anzapower.webs.com/temp1.swf

^ Click and see for yourself...

Keep clicking, at some point you do find two or more results that don't end up in the same place

Edited April 13, 2010 by qwe qwe

[superprismatic]

Man do I love ActionScript: http://anzapower.webs.com/temp1.swf

^ Click and see for yourself...

Keep clicking, at some point you do find two or more results that don't end up in the same place

You may have noticed that the example I used in the OP has 3

possible ending positions. I tried very hard to find one which

had 4 or more. I failed. Can you construct an array which has

4 or more possible ending positions?

[Guest]

You may have noticed that the example I used in the OP has 3

possible ending positions. I tried very hard to find one which

had 4 or more. I failed. Can you construct an array which has

4 or more possible ending positions?

The array is made and shuffled through a shuffling script I made up, it's always random, It's a bit hard to make one which doesn't have all the paths crossing cause as you can see there's a pretty high statistical chance for them to do...

One thing to add, the number of total different possible arrays of such would be (100!)/((10!)^10), I'll leave that for you to calculate...

[Guest]

You may have noticed that the example I used in the OP has 3

possible ending positions. I tried very hard to find one which

had 4 or more. I failed. Can you construct an array which has

4 or more possible ending positions?

With equal probabilities.


2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

2 4 8 3 5 6 7 1 9 10

Edited April 14, 2010 by Tuckleton

[Guest]

hey it's possible!

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[superprismatic]

hey it's possible!

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

[10,10,10,10,10,10,10,10,10]

It's supposed to have ten of each number from 1 to 10. So far, Tuckleton has the record. I'd like to know what the maximum really is.

[Guest]

5 is the maximum number of paths possible. The shortest number of squares a path must traverse, by starting on (0,9) and ending exactly one square outside the array, is 91. The next shortest path is 92 squares and starts on (0,8) since (0,9) is taken. The next shortest path starts on (0,7) and is 93 squares and so on.

If 6 paths existed then combined they would need to cover a minimum of 561 squares. Even ignoring how the paths might be arranged, using all our numbers we can only cover 550 squares (since no 2 paths can share the same number).

Now if only I could solve the original problem

Edited April 15, 2010 by Tuckleton

[Guest]

5 is the maximum number of paths possible. The shortest number of squares a path must traverse, by starting on (0,9) and ending exactly one square outside the array, is 91. The next shortest path is 92 squares and starts on (0,8) since (0,9) is taken. The next shortest path starts on (0,7) and is 93 squares and so on.

If 6 paths existed then combined they would need to cover a minimum of 561 squares. Even ignoring how the paths might be arranged, using all our numbers we can only cover 550 squares (since no 2 paths can share the same number).

Now if only I could solve the original problem

Nice, that's proving why 5 paths are the maximum, now we need a way to calculate the chances...

I say we build a super comp that'll try out all (100!)/(10!*10!)combinations and sum them up...XD

Edited April 15, 2010 by Anza Power

[Guest]

Sorry for double posting but I just got the number of possizble squares:

2.35707458939304*1e92

Umm............I'm just gonna sit in the corner and let other do the suggesting...

[superprismatic]

5 is the maximum number of paths possible. The shortest number of squares a path must traverse, by starting on (0,9) and ending exactly one square outside the array, is 91. The next shortest path is 92 squares and starts on (0,8) since (0,9) is taken. The next shortest path starts on (0,7) and is 93 squares and so on.

If 6 paths existed then combined they would need to cover a minimum of 561 squares. Even ignoring how the paths might be arranged, using all our numbers we can only cover 550 squares (since no 2 paths can share the same number).

Now if only I could solve the original problem

Please expand your proof. I can't see how the first paragraph relates to the second. The proof is just too terse for me. I would like to understand it. Thanks.

[Guest]

91+92+93+94+95+96 = 561.

1+2+3+4+5+6+7+8+9+10 = 55, 55*10 = 550.

561 > 550.

[Guest]

Please expand your proof. I can't see how the first paragraph relates to the second. The proof is just too terse for me. I would like to understand it. Thanks.

You have all the numbers from 1-10 ten times each, do the total and that should sum up to 550.

Now, lets say you have 10 different paths each starting from n (1≤n≤10) and end at 90+p (1≤p≤10 which means 91≤90+p≤100), so each path goes from (1-10) to (91-100), so they all take up 90+p-n, the sum of all the values of p minus all the values of n is 0, so the sum of all the paths is (90+p-n)*10=90*10=900! the sum of all the squares that Tuckleton exaplained (550) is not enough to cover such area.

Another proof why 10 can't be is this: for 10 different paths you need them never to cross each other, right? so the first tile has to jump over all the other tiles into tile 11, the second has to jump to 12, 3rd to 13.....and the tenth would eventually have only tile 20 as the nearest, Then they find themselves exactly at the same situation before (instead of 1-10 they're in 11-20) and they've used up all the 10's, the only possible way for 10 different paths is an array entirely made out of 10's,but that is against the rules...

Edited April 16, 2010 by Anza Power

[Guest]

Please expand your proof. I can't see how the first paragraph relates to the second. The proof is just too terse for me. I would like to understand it. Thanks.

Sorry, I never was good at formal proofs.

So the first paragraph talks about how the shortest possible path will start on (0,9) and end just outside the boundaries of the array, which is 91 steps away. Whatever form this path takes, the sum of the digits landed on during the journey must be equal to at least 91. Assume we've created such a path.

Now we want a second path. But since (0,9) is taken this path must begin on (0,8) which means it must cover a distance of 92 steps to end just outside the array. Whatever form this path takes, the sum of the digits landed on during the journey must be equal to at least 92. Assume we've managed to create such a path that doesn't share a square with the first path.

Now we want a third path. But since (0,9) and (0,8) are taken this path must begin on (0,7) which means it must cover a distance of 93 steps to end just outside the array. Whatever form this path takes, the sum of the digits landed on during the journey must be equal to at least 93. Assume we've managed to create such a path that doesn't share a square with the first two paths.

Continue this reasoning up to 6 paths. Now we have 6 paths, the sum of the numbers of each adding up to 91,92,93,94,95 and 96 respectively for a total sum of 561. Because no path can share a square with any of the other paths and remain unique, any number used in one path cannot be reused for another of the paths. But even using all 100 of our numbers we only get a total sum of 550 squares [(1+2+3+4+5+6+7+8+9+10)*10].

[superprismatic]

Thanks, Phillip1882, Anza Power, and Tuckleton. It makes

perfect sense now. I guess that the idea was so simple

and elegant that it flew right over my head! This is

really a very nice proof!

I've done a large Monte Carlo run on this problem and

it seems that two people will end up at the same spot

about 97.4% of the time. I don't have a theoretical

value, though.

[Quantum.Mechanic]

I FOUND SOMETHING!

I wrote a script in Flash that'll randomize an array just like in the riddle and test out all the starting points where they lead, here's what I got for 3 tries:

Try #1

Matrix:

1 2 1 6 2 2 7 9 3 3

2 1 6 2 2 7 9 3 3 8

1 6 2 2 7 9 3 3 8 10

6 2 2 7 9 3 3 8 10 10

2 2 7 9 3 3 8 10 10 4

2 7 9 3 3 8 10 10 4 3

7 9 3 3 8 10 10 4 3 9

9 3 3 8 10 10 4 3 9 2

3 3 8 10 10 4 3 9 2 6

3 8 10 10 4 3 9 2 6 8

Pairs:

(1,99)

(2,99)

(3,99)

(4,99)

(5,99)

(6,99)

(7,99)

(8,99)

(9,99)

(10,99)

Try #2

Matrix:

10 6 3 9 9 4 4 5 2 9

6 3 9 9 4 4 5 2 9 6

3 9 9 4 4 5 2 9 6 10

9 9 4 4 5 2 9 6 10 9

9 4 4 5 2 9 6 10 9 5

4 4 5 2 9 6 10 9 5 7

4 5 2 9 6 10 9 5 7 8

5 2 9 6 10 9 5 7 8 5

2 9 6 10 9 5 7 8 5 3

9 6 10 9 5 7 8 5 3 3

Pairs:

(1,94)

(2,94)

(3,94)

(4,94)

(5,94)

(6,94)

(7,94)

(8,94)

(9,94)

(10,94)

Try #3

Matrix:

3 5 2 2 1 1 6 4 1 5

5 2 2 1 1 6 4 1 5 5

2 2 1 1 6 4 1 5 5 4

2 1 1 6 4 1 5 5 4 4

1 1 6 4 1 5 5 4 4 3

1 6 4 1 5 5 4 4 3 3

6 4 1 5 5 4 4 3 3 8

4 1 5 5 4 4 3 3 8 6

1 5 5 4 4 3 3 8 6 1

5 5 4 4 3 3 8 6 1 8

Pairs:

(1,97)

(2,97)

(3,97)

(4,97)

(5,97)

(6,97)

(7,97)

(8,97)

(9,97)

(10,97)

I'm going to check the code again to see if it's really working properly but I think that's kinda the answer, I had a feeling that no matter how you arrange the array ALL paths are gonna cross at some point, though I have no mathematical way to prove it...(yet =P)

Your arrays are very regular, and not balanced with equal counts of the numbers 1-10.

[Guest]

Your arrays are very regular, and not balanced with equal counts of the numbers 1-10.

Oh, thanks fr pointing that out, but it must've been cause by the output panel thing, if you want check the swf file which send the results to a text box instead: http://anzapower.webs.com/temp1.swf