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

Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 27th, 2018 at 4:42:02 PM permalink
You 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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
December 27th, 2018 at 4:49:23 PM permalink

(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).

RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
December 27th, 2018 at 5:01:31 PM permalink
Edit nope I’m wrong and it’s not even close to be close.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 27th, 2018 at 5:08:28 PM permalink
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.

As you pointed out, the answer for the general case of an nxn square is combin(2*(n-1),n-1). In the case of a 10x10 square, it is combin(18,9)=48620. Why does that work? The drunk has to have some 18-move sequence of down and right moves. The down moves can be represented by picking 9 out of the 18 steps. The number of ways to pick 9 out of 18 is combin(18,9).
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
December 27th, 2018 at 5:47:36 PM permalink
Quote: Wizard

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.


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.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 27th, 2018 at 6:16:14 PM permalink
Quote: ThatDonGuy

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.



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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 27th, 2018 at 6:22:17 PM permalink
I 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?
Climate Casino: https://climatecasino.net/climate-casino/
BleedingChipsSlowly
BleedingChipsSlowly
  • Threads: 23
  • Posts: 1033
Joined: Jul 9, 2010
December 28th, 2018 at 6:49:18 PM permalink
Quote: teliot

I 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?

1134?

$ 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

“You don’t bring a bone saw to a negotiation.” - Robert Jordan, former U.S. ambassador to Saudi Arabia
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 28th, 2018 at 8:52:27 PM permalink
Quote: BleedingChipsSlowly

1134?

Sorry, not even close. Combinatorics are not relevant to this problem.
Climate Casino: https://climatecasino.net/climate-casino/
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 28th, 2018 at 9:06:40 PM permalink
10946



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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
December 28th, 2018 at 11:52:03 PM permalink
Quote: Wizard

10946



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.
BleedingChipsSlowly
BleedingChipsSlowly
  • Threads: 23
  • Posts: 1033
Joined: Jul 9, 2010
December 29th, 2018 at 4:35:15 AM permalink
Quote: teliot

Sorry, not even close. Combinatorics are not relevant to this problem.

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.


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.
“You don’t bring a bone saw to a negotiation.” - Robert Jordan, former U.S. ambassador to Saudi Arabia
unJon
unJon
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
December 29th, 2018 at 4:54:47 AM permalink
Quote: Wizard

10946



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
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 29th, 2018 at 5:27:31 AM permalink
Quote: teliot

Sorry, 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
I heart Crystal Math.
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 29th, 2018 at 5:38:03 AM permalink
Quote: BleedingChipsSlowly

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.


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.
I heart Crystal Math.
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 6:28:08 AM permalink
Quote: Wizard

10946



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.

You get credit for the first correct answer if your program will also compute the answer for a distance of 70 without crashing. :)
Climate Casino: https://climatecasino.net/climate-casino/
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 6:33:43 AM permalink
Quote: unJon


I get the same answer. It’s a Fibonacci sequence.

Exactly!

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.
Last edited by: teliot on Dec 29, 2018
Climate Casino: https://climatecasino.net/climate-casino/
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 6:38:12 AM permalink
Quote: BleedingChipsSlowly

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.

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.
Climate Casino: https://climatecasino.net/climate-casino/
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
Thanked by
CrystalMath
December 29th, 2018 at 6:59:19 AM permalink
Quote: CrystalMath

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

This is a restatement of the fact that the diagonal sums of Pascal's Triangle are Fibonacci numbers.

http://gofiguremath.org/wp-content/uploads/2013/12/Fibonacci-in-Pascal.png
Climate Casino: https://climatecasino.net/climate-casino/
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
December 29th, 2018 at 8:39:21 AM permalink
Quote: RS

I’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

BleedingChipsSlowly
BleedingChipsSlowly
  • Threads: 23
  • Posts: 1033
Joined: Jul 9, 2010
December 29th, 2018 at 8:51:48 AM permalink
Quote: teliot

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.

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. :-)
“You don’t bring a bone saw to a negotiation.” - Robert Jordan, former U.S. ambassador to Saudi Arabia
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 29th, 2018 at 8:54:24 AM permalink
Quote: Wizard

You have a 10x10 grid. A drunk starts...

How 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
I Heart Vi Hart
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 29th, 2018 at 9:08:18 AM permalink
Quote: mustangsally

How 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.
I heart Crystal Math.
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
Thanked by
BleedingChipsSlowly
December 29th, 2018 at 9:24:52 AM permalink
Quote: BleedingChipsSlowly

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. :-)



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 heart Crystal Math.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 29th, 2018 at 10:17:00 AM permalink
Quote: CrystalMath

He did say that the drunk could only move right or down. My first thought was the same as yours, though.

I guess the drunk for the question is a very talented drunk.

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
I Heart Vi Hart
cyberbabble
cyberbabble
  • Threads: 2
  • Posts: 85
Joined: Mar 24, 2013
December 29th, 2018 at 10:23:52 AM permalink
While you guys are watching drunks stumble down the street, a Japanese amoeba is teaching people how to solve the Traveling Salesman Problem.
At least, this article says so.

https://www.popularmechanics.com/science/math/a25686417/amoeba-math/
BleedingChipsSlowly
BleedingChipsSlowly
  • Threads: 23
  • Posts: 1033
Joined: Jul 9, 2010
Thanked by
CrystalMath
December 29th, 2018 at 11:38:44 AM permalink
Quote: CrystalMath

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.

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!)



$ 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
$

“You don’t bring a bone saw to a negotiation.” - Robert Jordan, former U.S. ambassador to Saudi Arabia
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 1:30:39 PM permalink
Quote: mustangsally

On average how many steps would it take to get to 20 steps? again with a random choice

14.5957427370729
Last edited by: teliot on Dec 29, 2018
Climate Casino: https://climatecasino.net/climate-casino/
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 29th, 2018 at 4:55:30 PM permalink
Yup, 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
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 29th, 2018 at 4:56:55 PM permalink
Quote: mustangsally

On average how many steps would it take to get to 20 steps? again with a random choice


Quote: teliot

14.5957427370729


I get this
looks like 13 5/9 but Excel spits out 13.55555534
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
it should be 18, always 18 steps. How could a drunk even do that?
I Heart Vi Hart
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 5:07:33 PM permalink
Here 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
Climate Casino: https://climatecasino.net/climate-casino/
unJon
unJon
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
December 29th, 2018 at 5:11:13 PM permalink
Quote: Wizard

Yup, 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.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
unJon
unJon
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
December 29th, 2018 at 5:12:52 PM permalink
Quote: teliot

Here 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?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 29th, 2018 at 5:15:42 PM permalink
Quote: teliot

Here 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

well, at first thought
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
Last edited by: mustangsally on Dec 29, 2018
I Heart Vi Hart
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 5:17:24 PM permalink
Quote: unJon

Quote: teliot

Here 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?

Except, if you are at 19, then each step isn't equally likely. Other than that, you may be on to something here!
Climate Casino: https://climatecasino.net/climate-casino/
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 29th, 2018 at 5:20:53 PM permalink
Quote: mustangsally

Quote: teliot

Here 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

well, at first thought
one could say
20/1.5 (average step) = 13 1/3 steps
my simulation showed 13.556 steps

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.
Climate Casino: https://climatecasino.net/climate-casino/
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 29th, 2018 at 5:22:42 PM permalink
Quote: Wizard

You have a 10x10 grid. A drunk starts...



Quote: mustangsally

How 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.
I heart Crystal Math.
unJon
unJon
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
December 29th, 2018 at 5:23:46 PM permalink
Quote: teliot

Quote: unJon

Quote: teliot

Here 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?

Except, if you are at 19, then each step isn't equally likely. Other than that, you may be on to something here!

Good point on step 19. That would explain why Sally’s simulation kicks out a slightly higher number than 20/1.5.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 29th, 2018 at 5:35:00 PM permalink
Quote: unJon

Good point on step 19. That would explain why Sally’s simulation kicks out a slightly higher number than 20/1.5.

my 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
I Heart Vi Hart
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
Thanked by
mustangsally
December 29th, 2018 at 5:35:46 PM permalink
Assuming each step length is randomly chosen, I calculate 13.5555553436 steps, on average.
I heart Crystal Math.
unJon
unJon
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
Thanked by
CrystalMath
December 29th, 2018 at 5:46:20 PM permalink
Quote: mustangsally

my 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.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
onenickelmiracle
onenickelmiracle
  • Threads: 212
  • Posts: 8277
Joined: Jan 26, 2012
December 30th, 2018 at 12:29:48 AM permalink
http://mentalfloss.com/article/30987/10-worlds-most-expensive-beers
I am a robot.
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 30th, 2018 at 8:01:12 AM permalink
Quote: unJon

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?
Climate Casino: https://climatecasino.net/climate-casino/
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 30th, 2018 at 8:29:08 AM permalink
Quote: teliot

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?

this 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
I Heart Vi Hart
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 30th, 2018 at 8:36:37 AM permalink
Quote: mustangsally

this 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

Awesome! Quick note, it can never be exactly 2/3 for any fixed n, though that is obviously the limiting value, since the average step length is 1.5. Starting out, the probability of landing on 1 is 1/2, of 2 is 3/4, etc. ... My simulation of 1B trials gives 0.66666495
Climate Casino: https://climatecasino.net/climate-casino/
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
December 30th, 2018 at 8:47:56 AM permalink
Quote: teliot

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?


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

teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 30th, 2018 at 9:12:58 AM permalink
Quote: ThatDonGuy

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.
Climate Casino: https://climatecasino.net/climate-casino/
mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
December 30th, 2018 at 9:51:10 AM permalink
Quote: mustangsally

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

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.69051935
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
I Heart Vi Hart
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
January 4th, 2019 at 1:25:26 AM permalink
Quote: Wizard

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

Sorry for the late reply. Here are two alternate solutions.

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.
Last edited by: Ace2 on Jan 4, 2019
It’s all about making that GTA
  • Jump to: