Random path in a grid
Poll
| No votes (0%) | |||
| No votes (0%) | |||
 | 1 vote (14.28%) | ||
| No votes (0%) | |||
| | 1 vote (14.28%) | ||
| | 1 vote (14.28%) | ||
| | 2 votes (28.57%) | ||
| | 1 vote (14.28%) | ||
| | 3 votes (42.85%) | ||
| | 3 votes (42.85%) |
7 members have voted
As usual, please put answers in spoiler tags.
(18)C(9), or 48,620
The grid is Pascal's Triangle turned 45 degrees counterclockwise
To clarify:
Label the grid locations (X,Y), where X and Y can be from 1 to 10
There is 1 way to start at (1,1); there is 1 way to get to (1,2), 1 to get to (1,3), and so on through (1,10).
There is also 1 way to get to (2,1), 1 to get to (3,1), and so on through (10,1).
There are 2 ways to get to (2,2); 1 via (1,2), and 1 via (2,1).
There are 3 ways to get to (2,3); 1 via (1,3) and 2 via (2,2).
In fact, the number of ways to get to (X,Y) = the number to get to (X-1, Y) (and then you move down) + the number to get to (X, Y-1) (and then you move to the right).
This is also how Pascal's Triangle can be formed; row N of Pascal's triangle (where the top row is row 0) has (N)C(0), (N)C(1), and so on through (N)C(N).
If you turn the grid 45 degrees, what was the top left is row 0, column 0, and what was the bottom right is row 18, column 9, or (18)C(9).
Quote: ThatDonGuy
(18)C(9), or 48,620
The grid is Pascal's Triangle turned 45 degrees counterclockwise
To clarify:
Label the grid locations (X,Y), where X and Y can be from 1 to 10
There is 1 way to start at (1,1); there is 1 way to get to (1,2), 1 to get to (1,3), and so on through (1,10).
There is also 1 way to get to (2,1), 1 to get to (3,1), and so on through (10,1).
There are 2 ways to get to (2,2); 1 via (1,2), and 1 via (2,1).
There are 3 ways to get to (2,3); 1 via (1,3) and 2 via (2,2).
In fact, the number of ways to get to (X,Y) = the number to get to (X-1, Y) (and then you move down) + the number to get to (X, Y-1) (and then you move to the right).
This is also how Pascal's Triangle can be formed; row N of Pascal's triangle (where the top row is row 0) has (N)C(0), (N)C(1), and so on through (N)C(N).
If you turn the grid 45 degrees, what was the top left is row 0, column 0, and what was the bottom right is row 18, column 9, or (18)C(9).
Yep, another beer to that guy named Don. Congratulations! I'm going to have to take you to Germany for Oktoberfest to clear my tab with you.
Quote: WizardYep, another beer to that guy named Don. Congratulations! I'm going to have to take you to Germany for Oktoberfest to clear my tab with you.
Is there going to be a Spring Fling this year? I'll try to make it down for that, where I seem to recall that you promised that you would "clear my tab" by buying a round for the group.
Quote: ThatDonGuyIs there going to be a Spring Fling this year? I'll try to make it down for that, where I seem to recall that you promised that you would "clear my tab" by buying a round for the group.
Yes, I'm sure there will be. I do recall that deal to buy a round for the group to clear my debt, which is nice of you.
We should discuss a date for that -- in another thread.
You can take a small step of length 1 or a big step of length 2. How many different ways can you walk a total length of 20?
Quote: teliotI hadn't heard this one before, but when I read it I was immediately reminded of this problem ....
You can take a small step of length 1 or a big step of length 2. How many different ways can you walk a total length of 20?
$ cat ways.java
class ways {
public static void main(String args[]) {
Integer distance = 20;
System.out.println(ways(distance));
}
private static Integer ways(Integer distance) {
Integer total = 0;
for (Integer ds = 0; ds <= Math.floor(distance/2); ds++) {
Integer ts = distance - ds;
// ds = double steps, ts = total steps, total += C(ts,ds)
total += factorial(ts) / (factorial(ds) * factorial(ts-ds));
}
return total;
}
private static Integer factorial(Integer n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
}
$ javac ways.java
$ java ways
1134
Sorry, not even close. Combinatorics are not relevant to this problem.Quote: BleedingChipsSlowly1134?
void main(void)
{
t=0;
for (i=0; i<=20; i++)
{
j=10-(i/2);
t+=combin(i+j,i);
}
printf("%i\n",i);
}
int combin(int x, int y)
{
c=fact(x+y)/(fact(x)*fact(y));
return c;
}
int fact(x)
{
int f=1;
for (int i=1; i<=x; i++)
f*=i;
return f;
}
// I'm sure there is a more elegant way to put this, if I'm even right.
Quote: Wizard10946
void main(void)
{
t=0;
for (i=0; i<=20; i++)
{
j=10-(i/2);
t+=combin(i+j,i);
}
printf("%i\n",i);
}
int combin(int x, int y)
{
c=fact(x+y)/(fact(x)*fact(y));
return c;
}
int fact(x)
{
int f=1;
for (int i=1; i<=x; i++)
f*=i;
return f;
}
// I'm sure there is a more elegant way to put this, if I'm even right.
I’m just waiting for don to prove it using primes, Fibonacci sequence, 2n, etc.
Thanks for responding, teliot. While it's disappointing to arrive at an incorrect solution, I'm hoping to learn from my error. Perhaps I didn't understand the problem. For 6 feet, the method I used generates 13 as the number of ways to navigate that length using combinations of short (1) and long (2) steps. I worked that out by hand and also arrived at a solution set of 13. If you (or anyone else) could let me know what elements are missing from that solution set, I'll grab a cup of coffee and rethink my logic.Quote: teliotSorry, not even close. Combinatorics are not relevant to this problem.
SSSSSS
LSSSS
SLSSS
SSLSS
SSSLS
SSSSL
LLSS
LSLS
LSSL
SLLS
SLSL
SSLL
LLL
If necessary, I could create the solution set using my method for 20 feet, but I'm hoping a lesser example will suffice.
Quote: Wizard10946
void main(void)
{
t=0;
for (i=0; i<=20; i++)
{
j=10-(i/2);
t+=combin(i+j,i);
}
printf("%i\n",i);
}
int combin(int x, int y)
{
c=fact(x+y)/(fact(x)*fact(y));
return c;
}
int fact(x)
{
int f=1;
for (int i=1; i<=x; i++)
f*=i;
return f;
}
// I'm sure there is a more elegant way to put this, if I'm even right.
I get the same answer. It’s a Fibonacci sequence.
D=distance
S=total number of ways to cover distance
D | S
1 | 1
2 | 2
3 | 3
4 | 5
5 | 8
6 | 13
. . .
20 | 10,946
Quote: teliotSorry, not even close. Combinatorics are not relevant to this problem.
I solved it with combinatorics.
You could take 20 single +0 doubles which gives 20c0 ways.
18 single + 1 double = 19c1 ways
16 single + 2 double = 18c2 ways
...
20c0 + 19c1 + 18c2 + 17c3 + 16c4 + 15c5 + 14c6 + 13c7 + 12c8 + 11c9 + 10c10 = 10946
Quote: BleedingChipsSlowlyThanks for responding, teliot. While it's disappointing to arrive at an incorrect solution, I'm hoping to learn from my error. Perhaps I didn't understand the problem. For 6 feet, the method I used generates 13 as the number of ways to navigate that length using combinations of short (1) and long (2) steps. I worked that out by hand and also arrived at a solution set of 13. If you (or anyone else) could let me know what elements are missing from that solution set, I'll grab a cup of coffee and rethink my logic.
SSSSSS
LSSSS
SLSSS
SSLSS
SSSLS
SSSSL
LLSS
LSLS
LSSL
SLLS
SLSL
SSLL
LLL
If necessary, I could create the solution set using my method for 20 feet, but I'm hoping a lesser example will suffice.
I think you are overloading your integers with the factorial calculations.
You get credit for the first correct answer if your program will also compute the answer for a distance of 70 without crashing. :)Quote: Wizard10946
void main(void)
{
t=0;
for (i=0; i<=20; i++)
{
j=10-(i/2);
t+=combin(i+j,i);
}
printf("%i\n",i);
}
int combin(int x, int y)
{
c=fact(x+y)/(fact(x)*fact(y));
return c;
}
int fact(x)
{
int f=1;
for (int i=1; i<=x; i++)
f*=i;
return f;
}
// I'm sure there is a more elegant way to put this, if I'm even right.
Exactly!Quote: unJon
I get the same answer. It’s a Fibonacci sequence.
The easiest way to see this is to ask what the state is after you take your first step. Let W(n) be the number of ways to walk a distance n. Then W(1) = 1 and W(2) = 2 (either one big step or two small steps).
After your first step, you have either a distance of n-1 or n-2 left and you have taken 1 step. So W(n) = W(n-1) + W(n-2).
For the programmers, good coding! It would never have occurred to me to try to answer the question that way. Then again, your programs will all fail for large enough n. Well, everything fails for large enough n, but not all n's are created equally.
For the combinatorics, yeah, I guess so -- but it does somehow seem less elegant.
It was my mistake to say it couldn't be done with combinatorics. I am not sure why your program didn't work, I didn't examine it that closely.Quote: BleedingChipsSlowlyThanks for responding, teliot. While it's disappointing to arrive at an incorrect solution, I'm hoping to learn from my error. Perhaps I didn't understand the problem. For 6 feet, the method I used generates 13 as the number of ways to navigate that length using combinations of short (1) and long (2) steps. I worked that out by hand and also arrived at a solution set of 13. If you (or anyone else) could let me know what elements are missing from that solution set, I'll grab a cup of coffee and rethink my logic.
This is a restatement of the fact that the diagonal sums of Pascal's Triangle are Fibonacci numbers.Quote: CrystalMathI solved it with combinatorics.
You could take 20 single +0 doubles which gives 20c0 ways.
18 single + 1 double = 19c1 ways
16 single + 2 double = 18c2 ways
...
20c0 + 19c1 + 18c2 + 17c3 + 16c4 + 15c5 + 14c6 + 13c7 + 12c8 + 11c9 + 10c10 = 10946
http://gofiguremath.org/wp-content/uploads/2013/12/Fibonacci-in-Pascal.png
Quote: RSI’m just waiting for don to prove it using primes, Fibonacci sequence, 2n, etc.
There are 11 different ways to make a distance of 20:
20 1s
18 1s, 1 2
16 1s, 2 2s
14 1s, 3 2s
...
2 1s, 9 2s
10 2s
Start with 20 1s; there is 1 way to do this
For 18 1s and a 2, there are 19 ways to place the 2 among the 1s (before 0, 1, 2, ..., 18 1s)
For 16 1s and two 2s, there are 17 ways to place the first (leftmost) 2, and if the first 2 is in position P1 (numbering the positions from right to left), there are P1 ways to place the second two; there are 17 + 16 + 15 + 14 + ... + 1 = (18)C(2)
For 14 1s and three 2s, there are 15 ways to place the "first" (leftmost) 2, P1 ways to place the second 2, and P2 ways to place the third 2; the total is (15 + 14 + 13 + ... + 1) + (14 + 13 + 12 + ... + 1) + ... + (2 + 1) + 1 = (16)C(2) + (15)C(2) + ... + (2)C(2) = (17)C(3)
For 12 1s and four 2s, there are 13 ways to place the "first" (leftmost) 2; the total is ((13 + 12 + 11 + ... + 1) + (12 + 11 +... + 1) + ... + (2 + 1) + 1) + ((12 + 11 + ... + 1) + (11 + 10 + ... + 1) + ... + 1) + ... + ((2 + 1) + 1) + 1 = (15)C(3) + (14)C(3) + ... + (3)C(3) = (16)C(4).
Similarly, 10 1s and five 2s has (15)C(5) ways, 8 1s and six 3s has (14)C(6), and so on
The total is 1 + (19)C(1) + (18)C(2) + (17)C(3) + ... + (11)C(9) + (10)C(10) = 10,946
Proof that (N)C(N) + (N+1)C(N) + (N+2)C(N) + ... + (N+K)C(N) = (N+K+1)C(N+1) available on request
Thanks for the follow up. My method's solutions match the Fibonacci series until 14 feet. For 14 feet the Fibonacci answer is 610 and mine is 601. I'll work on it some more when I have time. Right now Mrs. Chips says I've spent enough time with math fun. :-)Quote: teliotIt was my mistake to say it couldn't be done with combinatorics. I am not sure why your program didn't work, I didn't examine it that closely.
How drunk? How large is the grid?Quote: WizardYou have a 10x10 grid. A drunk starts...
I doubt any drunk could complete the journey.
with the random choice
On average how many steps would it take?
the 20 step question with 1 or 2 steps.
"You can take a small step of length 1 or a big step of length 2. How many different ways can you walk a total length of 20?"
On average how many steps would it take to get to 20 steps? again with a random choice
Sally
Quote: mustangsallyHow drunk? How large is the grid?
I doubt any drunk could complete the journey.
with the random choice
On average how many steps would it take?
the 20 step question with 1 or 2 steps.
"You can take a small step of length 1 or a big step of length 2. How many different ways can you walk a total length of 20?"
On average how many steps would it take to get to 20 steps? again with a random choice
Sally
He did say that the drunk could only move right or down. My first thought was the same as yours, though.
Quote: BleedingChipsSlowlyThanks for the follow up. My method's solutions match the Fibonacci series until 14 feet. For 14 feet the Fibonacci answer is 610 and mine is 601. I'll work on it some more when I have time. Right now Mrs. Chips says I've spent enough time with math fun. :-)
I think you missed my previous answer. You are overloading the integer. Once you exceed 2^31 on any factorial, your answer will be off.
The reason it still works for 13, (13!=6,277,020,800), is because you are taking the overloaded int and dividing by the same number, giving the result of 1, which is correct for 13c0.
I guess the drunk for the question is a very talented drunk.Quote: CrystalMathHe did say that the drunk could only move right or down. My first thought was the same as yours, though.
This singer/dancer makes lots of steps (during the song) on a large stage but most times is back to where he started.
How many steps? Hard to count
at 5 minutes the singer makes lots of steps
Sally
At least, this article says so.
https://www.popularmechanics.com/science/math/a25686417/amoeba-math/
Yes, I did miss your previous post. My bad, as your analysis was spot on and it would have saved me a lot of time. I changed the program to use 64-bit integers and I now get the same results as others. I am happy to find out my programming logic was right, but disappointed that I missed the overload condition. I should know better. I was being lazy and decided I would do it quick and dirty, then attend to any exceptions thrown. Lesson learned. Again. Once more, thanks very much for your help, CrystalMath! (Thank goodness I didn't have to go to BigInteger. Gave that a try, what a mess!)Quote: CrystalMathI think you missed my previous answer. You are overloading the integer. Once you exceed 2^31 on any factorial, your answer will be off.
The reason it still works for 13, (13!=6,277,020,800), is because you are taking the overloaded int and dividing by the same number, giving the result of 1, which is correct for 13c0.
$ cat ways.java
class ways {
public static void main(String args[]) {
for (Long distance = 1L; distance <= 20L; distance++) {
System.out.println(distance + " " + ways(distance));
}
}
private static Long ways(Long distance) {
Long total = 0L;
for (Long ds = 0L; ds <= Math.floor(distance/2L); ds++) {
Long ts = distance - ds;
// ds = double steps, ts = total steps, total += C(ts,ds)
total += factorial(ts) / (factorial(ds) * factorial(ts-ds));
}
return total;
}
private static Long factorial(Long n) {
if (n == 0L) {
return 1L;
} else {
return n * factorial(n-1L);
}
}
}
$ javac ways.java
$ java ways
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
$
Quote: mustangsallyOn average how many steps would it take to get to 20 steps? again with a random choice
| Distance | Possible steps |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
| 11 | 89 |
| 12 | 144 |
| 13 | 233 |
| 14 | 377 |
| 15 | 610 |
| 16 | 987 |
| 17 | 1,597 |
| 18 | 2,584 |
| 19 | 4,181 |
| 20 | 6,765 |
| 21 | 10,946 |
| 22 | 17,711 |
| 23 | 28,657 |
| 24 | 46,368 |
| 25 | 75,025 |
| 26 | 121,393 |
| 27 | 196,418 |
| 28 | 317,811 |
| 29 | 514,229 |
| 30 | 832,040 |
| 31 | 1,346,269 |
| 32 | 2,178,309 |
| 33 | 3,524,578 |
| 34 | 5,702,887 |
| 35 | 9,227,465 |
| 36 | 14,930,352 |
| 37 | 24,157,817 |
| 38 | 39,088,169 |
| 39 | 63,245,986 |
| 40 | 102,334,155 |
| 41 | 165,580,141 |
| 42 | 267,914,296 |
| 43 | 433,494,437 |
| 44 | 701,408,733 |
| 45 | 1,134,903,170 |
| 46 | 1,836,311,903 |
| 47 | 2,971,215,073 |
| 48 | 4,807,526,976 |
| 49 | 7,778,742,049 |
| 50 | 12,586,269,025 |
| 51 | 20,365,011,074 |
| 52 | 32,951,280,099 |
| 53 | 53,316,291,173 |
| 54 | 86,267,571,272 |
| 55 | 139,583,862,445 |
| 56 | 225,851,433,717 |
| 57 | 365,435,296,162 |
| 58 | 591,286,729,879 |
| 59 | 956,722,026,041 |
| 60 | 1,548,008,755,920 |
| 61 | 2,504,730,781,961 |
| 62 | 4,052,739,537,881 |
| 63 | 6,557,470,319,842 |
| 64 | 10,610,209,857,723 |
| 65 | 17,167,680,177,565 |
| 66 | 27,777,890,035,288 |
| 67 | 44,945,570,212,853 |
| 68 | 72,723,460,248,141 |
| 69 | 117,669,030,460,994 |
| 70 | 190,392,490,709,135 |
Quote: mustangsallyOn average how many steps would it take to get to 20 steps? again with a random choice
Quote: teliot14.5957427370729
I get this
Here is my Excel sheet in Google for those that want to looks
https://goo.gl/vbMXgT
Sally
for the average number of steps the Wizard's drunk takes in his puzzle
My answer is simply the quotient: 159765/10946
Quote: WizardYup, it is Fibonacci. I should have seen that.
Distance Possible steps 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 144 13 233 14 377 15 610 16 987 17 1,597 18 2,584 19 4,181 20 6,765 21 10,946 22 17,711 23 28,657 24 46,368 25 75,025 26 121,393 27 196,418 28 317,811 29 514,229 30 832,040 31 1,346,269 32 2,178,309 33 3,524,578 34 5,702,887 35 9,227,465 36 14,930,352 37 24,157,817 38 39,088,169 39 63,245,986 40 102,334,155 41 165,580,141 42 267,914,296 43 433,494,437 44 701,408,733 45 1,134,903,170 46 1,836,311,903 47 2,971,215,073 48 4,807,526,976 49 7,778,742,049 50 12,586,269,025 51 20,365,011,074 52 32,951,280,099 53 53,316,291,173 54 86,267,571,272 55 139,583,862,445 56 225,851,433,717 57 365,435,296,162 58 591,286,729,879 59 956,722,026,041 60 1,548,008,755,920 61 2,504,730,781,961 62 4,052,739,537,881 63 6,557,470,319,842 64 10,610,209,857,723 65 17,167,680,177,565 66 27,777,890,035,288 67 44,945,570,212,853 68 72,723,460,248,141 69 117,669,030,460,994 70 190,392,490,709,135
Wiz, your table is offset by one. Two ways to do step 2 not 1 way. It’s Fibonacci starting at the second 1.
Quote: teliotHere is my math, Sally. I certainly could be wrong ... this was an intuitively obvious way to do this, but who knows ... Also, doesn't it seem reasonable that the answer should be close to (3/4)*n, since the average step will be about 1.5 steps in length (aside from boundary conditions)?
My answer is simply the quotient: 159765/10946
At a guess, teliot assumes each path to 20 is equally likely and Sally assumes at each step, it’s equally likely to be a long or short step?
well, at first thoughtQuote: teliotHere is my math, Sally. I certainly could be wrong ... this was an intuitively obvious way to do this, but who knows ... Also, doesn't it seem reasonable that the answer should be close to (3/4)*n, since the average step will be about 1.5 steps in length (aside from boundary conditions)?
My answer is simply the quotient: 159765/10946
one could say
20/1.5 (average step) = 13 1/3 steps
my simulation showed 13.556 steps and standard deviation of 1.2255
I show the distribution on my excel sheet in Google
here it is also
still a fun thought process
I had to use matrix math (Excel sheet is even easier)
Sally
Except, if you are at 19, then each step isn't equally likely. Other than that, you may be on to something here!Quote: unJonQuote: teliotHere is my math, Sally. I certainly could be wrong ... this was an intuitively obvious way to do this, but who knows ... Also, doesn't it seem reasonable that the answer should be close to (3/4)*n, since the average step will be about 1.5 steps in length (aside from boundary conditions)?
My answer is simply the quotient: 159765/10946
At a guess, teliot assumes each path to 20 is equally likely and Sally assumes at each step, it’s equally likely to be a long or short step?
I think we have the difference diagnosed by UnJ ... I am assuming each sequence is equally likely, you are assuming each step (length 1 or 2 at any give time) is equally likely.Quote: mustangsallywell, at first thoughtQuote: teliotHere is my math, Sally. I certainly could be wrong ... this was an intuitively obvious way to do this, but who knows ... Also, doesn't it seem reasonable that the answer should be close to (3/4)*n, since the average step will be about 1.5 steps in length (aside from boundary conditions)?
My answer is simply the quotient: 159765/10946
one could say
20/1.5 (average step) = 13 1/3 steps
my simulation showed 13.556 steps
Quote: WizardYou have a 10x10 grid. A drunk starts...
Quote: mustangsallyHow drunk? How large is the grid?
I doubt any drunk could complete the journey.
with the random choice
On average how many steps would it take?
Sally
Given a 10x10 grid, assuming a drunk could randomly make any move up/down/left/right within bounds, I get 543.1005217.
Good point on step 19. That would explain why Sally’s simulation kicks out a slightly higher number than 20/1.5.Quote: teliotExcept, if you are at 19, then each step isn't equally likely. Other than that, you may be on to something here!Quote: unJonQuote: teliotHere is my math, Sally. I certainly could be wrong ... this was an intuitively obvious way to do this, but who knows ... Also, doesn't it seem reasonable that the answer should be close to (3/4)*n, since the average step will be about 1.5 steps in length (aside from boundary conditions)?
My answer is simply the quotient: 159765/10946
At a guess, teliot assumes each path to 20 is equally likely and Sally assumes at each step, it’s equally likely to be a long or short step?
my sim and matrix was actually for getting at least 20 steps (one could get to 21 steps)Quote: unJonGood point on step 19. That would explain why Sally’s simulation kicks out a slightly higher number than 20/1.5.
well another day
off to catch an airplane.
How does one catch an airplane?
do not want to catch a cold!
Sally
Quote: mustangsallymy sim and matrix was actually for getting at least 20 steps (one could get to 21 steps)
well another day
off to catch an airplane.
How does one catch an airplane?
do not want to catch a cold!
Sally
Letting the sim go to at least 20 is equivalent to forcing a short step of on 19.
This leads to a question that I admit I have not answered. If you take steps of length 1 and 2 at random, what is the probability that you land exactly on 20?Quote: unJonLetting the sim go to at least 20 is equivalent to forcing a short step of on 19.
this is simple by looking at my worksheet cuz I had states 20 and 21 as absorbing states (ending states).Quote: teliotThis leads to a question that I admit I have not answered. If you take steps of length 1 and 2 at random, what is the probability that you land exactly on 20?
landing exactly on 21 is about 0.333333015 (looks like 1/3)
I see it also matched a simulation I did
this is similar (not exact) to the game of TROUBLE, trying to get that last game piece home
I love to play TROUBLE against one other person having 2 colors. You send yourself back to start many times.
Sally
Happy New Year
Quote: mustangsallythis is simple by looking at my worksheet cuz I had states 20 and 21 as absorbing states (ending states).
landing exactly on 20 is about 0.666666985 (looks like 2/3)
landing exactly on 21 is about 0.333333015 (looks like 1/3)
I see it also matched a simulation I did
this is similar (not exact) to the game of TROUBLE, trying to get that last game piece home
I love to play TROUBLE against one other person having 2 colors. You send yourself back to start many times.
Sally
Happy New Year
Quote: teliotThis leads to a question that I admit I have not answered. If you take steps of length 1 and 2 at random, what is the probability that you land exactly on 20?
It's very close to 2/3 - in fact, the higher the target is, the closer the probability gets to exactly 2/3.
Let PN be the probability of reaching the target from N steps away
P0 = 1
P1 = 1/2
PK = 1/2 PK-1 + 1/2 PK-2 for all K >= 2
As N approaches infinity, PN = 1/2 + 1/4 - 1/8 + 1/16 - 1/32 + ...
= 1/2 + 1/4 (1 + (-1/2) + (-1/2)2 + (-1/2)3 + ...)
= 1/2 + 1/4 (1 / (1 - (-1/2))
= 1/2+ 1/4 x 2/3
= 2/3
The exact answer for 20 is 1/2 + 1/4 - 1/8 + 1/16 - 1/32 + 1/64 - 1/128 + 1/256 - 1/512 + 1/1024 - 1/2048 + ... + 1/262144 - 1/524288
= 1/2 + 1/8 + 1/32 + 1/128 + ... + 1/524288
= 1/2 (1 + 1/4 + (1/4)2 + ... + (1/4)9)
= 1/2 (1 - (1/4)10) / (1 - 1/4)
= 1/2 x 4/3 x 1048575/1048576
= 1048575 / 1572864
Awesome.Quote: ThatDonGuyIt's very close to 2/3 - in fact, the higher the target is, the closer the probability gets to exactly 2/3.
Let PN be the probability of reaching the target from N steps away
P0 = 1
P1 = 1/2
PK = 1/2 PK-1 + 1/2 PK-2 for all K >= 2
As N approaches infinity, PN = 1/2 + 1/4 - 1/8 + 1/16 - 1/32 + ...
= 1/2 + 1/4 (1 + (-1/2) + (-1/2)2 + (-1/2)3 + ...)
= 1/2 + 1/4 (1 / (1 - (-1/2))
= 1/2+ 1/4 x 2/3
= 2/3
The exact answer for 20 is 1/2 + 1/4 - 1/8 + 1/16 - 1/32 + 1/64 - 1/128 + 1/256 - 1/512 + 1/1024 - 1/2048 + ... + 1/262144 - 1/524288
= 1/2 + 1/8 + 1/32 + 1/128 + ... + 1/524288
= 1/2 (1 + 1/4 + (1/4)2 + ... + (1/4)9)
= 1/2 (1 - (1/4)10) / (1 - 1/4)
= 1/2 x 4/3 x 1048575/1048576
= 1048575 / 1572864
because I did this some time ago, the average number of rolls (pop-a-matic) to get the 1st game piece HOME (1 of the 4 spots) in Trouble is 14.69051935Quote: mustangsallythis is similar (not exact) to the game of TROUBLE, trying to get that last game piece home
I love to play TROUBLE against one other person having 2 colors. You send yourself back to start many times.
Sally
Happy New Year
that includes getting the piece out (on a roll of a 6) then the mad dash around
each spot has a different probability of the 1st piece landing on it
1: 0.321455849
2: 0.273798572
3: 0.226172622
4: 0.178572957
looks close to 60/40 it lands on spot 1 or 2
btw, using a different die in a cup (could be a d10 for example)
really makes this game super fun and challenging
Sally
Sorry for the late reply. Here are two alternate solutions.Quote: WizardYou have a 10x10 grid. A drunk starts in the upper-left square and wants to reach the lower-right square. He is only allowed to move down and to the right. How many different paths can he take? For full credit, I'm looking for a mathematical expression of the answer and why it works, but just a number will get you partial credit. A beer to the first acceptable full answer and solution.
As usual, please put answers in spoiler tags.Have a nice day.
2^18 / (3 * pi^.5) =~ 49,300 possible paths.
Since the question is fundamentally: “if we flip a coin 18 times, what is the probability that exactly 9 heads appear?”. That probability is approximately 1 / (18 / 2 * pi)^.5 or ~ 18.806 % then multiply that by 2^18 possible permutations.
The exact answer to the coin question can be found by taking the integral from zero to infinity of :
(x/2)^17/ (9! * 8! * e^x) = 12,155 / 65,536
And multiplying that by 2^18 for the exact solution of 48,620.
Though the most straightforward exact answer must be combin (18,9) as posted previously.
