3 added 308 characters in body
source | link

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

So although this proves that it is possible to beat the dealer, it still might not be the ideal solution. I think there is a way to guarantee winning 3 or 4 euros by taking smaller initial steps and setting a margin of error so that the least profitable step in each series is still worth a couple euros.

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

So although this proves that it is possible to beat the dealer, it still might not be the ideal solution. I think there is a way to guarantee winning 3 or 4 euros by taking smaller initial steps and setting a margin of error so that the least profitable step in each series is still worth a couple euros.

2 deleted 62 characters in body
source | link

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

(I don't know why the latex stopped working down here)$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

(I don't know why the latex stopped working down here)

Some algebra leads to the closed form expression.

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

1
source | link

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

  1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

  1. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2) + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

(I don't know why the latex stopped working down here)

Some algebra leads to the closed form expression.