Progressive Spending 3

[vacunita]

This is a quirky little experiment I was shown the other day.

The object is to find the equation that will define the process with X amount of iterations.
For ease of understanding lets start with 3 iterations.

A Person has X amount of money when he enters a store. The store charges 1 dollar for entry. The Person then spends half of his remaining money inside the store. Exiting a store also costs 1 dollar. He does this 3 times

If he ends up with no money how much did he start with?

What if he did it 5 times? or 7? How much does the person need to start with based on the amount of iterations.

Notes:
1. Yes these stores charge for exit.
2. He can never be left without money inside the store. That is the last iteration ends with him having 1 dollar and using it to exit the final store.
3. At no time can he have change. Only integral dollar amounts.





----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[CajunCenturion]

==> find the equation that will define the process with X amount of iterations.
You'll need y dollars for x iterations, defined by the following:
[hide]y = 3 * (2^x - 1)[/hide]


--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
Wise men speak because they have something to say, fools because they have to say something. - Plato

 

[kwbMitel]

By my usual method of manually working out solutions and looking for patterns it looks like the following formula will work
[hide](2^^interations - 1) times 3 = Dollars required [/hide]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

Here is an easy proof using mathematical induction that the above answers are correct:

[hide]
To start the induction, we need to show that

y = 3 * (2^x - 1)

gives the correct amount when x=1. But 3 * (2¹ - 1) = 3 * (2 - 1) = 3 and $3 is, indeed the correct amount needed to pay $1 to enter a store, spend half of the remaining $2, and be left with the $1 needed to exit the store.

The second part of the induction is to prove that

y = 3 * (2^x - 1)

is the correct amount needed to visit x stores, under the inductive hypothesis that

y = 3 * (2^x-1 - 1)

is the correct amount needed to visit (x-1) stores. Visiting a store consists of three transactions - (1) paying the $1 entry fee, (2) spending half of the remaining money, and (3) paying the $1 exit fee.

(1) After paying the entry fee, the shopper has

3 * (2^x - 1) - 1
= 3 * 2^x - 4

dollars remaining.

(2) After spending half of the remaining money, the shopper has

(3 * 2^x - 4) / 2
= 3 * 2^x-1 - 2

dollars remaining

(3) After paying the $1 exit fee, the shopper has

(3 * 2^x-1 - 2) - 1
= 3 * 2^x-1 - 3
= 3 * (2^x-1 - 1)

dollars remaining, which by induction is exactly the amount needed to visit (x-1) stores. So the formula does, indeed, give the correct amount needed to visit x stores.
[/hide]

 

[vacunita]

Yes, they are correct.

You get a couple bears on me next time we meet in person.

I'll have to come up with something more convoluted next time.


----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[Olaf Doschke]

OK, CajunCenturion and kwbMitel gave the formula, but it seems to fall from the sky (o the cloud perhaps?). Not that it makes it wrong, as karl proves via mathematical induction. Taken aside all suspicion, still after that induction it's unclear how that formula could be derived. Let's see...

[hide]First of all, you can easily compute the needed amount reversing the process and starting with an amount of 0 dollars, N times adding 1, doubling, adding one again.

From that steps, the formula still doesn't spring to my eyes. So how can it be deducted in the first place, to then prove it's correct via induction?

First part: observation of the amounts after each visit (in reverse order).

1: (0+1)*2+1 = 3
2: (3+1)*2+1 = 9
3: (9+1)*2+1 = 21
4: (21+1)*2+1 = 45
5: (45+1)*2+1 = 93

Doubling in each iteration makes it plausible to compare these numbers with powers of 2. Pardon the following unusual short notation, but I think you get what it denotes:

1: 3 vs 2 (=2^1)
2: 9 vs 4 (=2^2)
3: 21 vs 8 (=2^3)
4: 45 vs 16 (=2^4)
5: 93 vs 32 (=2^5)

The factor of three is showing up here as a roundabout factor between the rounds results and the powers of two. That's still no good explanation, but here we go:

1: 3/3 = 1 vs 2
2: 9/3 = 3 vs 4
3: 21/3 = 7 vs 8
4: 45/3 = 15 vs 16
5: 93/3 = 31 vs 32

Now that's quite obvious 3*(2^iteations-1) and mathematical induction is a nice way proving that for any N visits.

Why the factor 3, though? As a first feeling the entry/exit fee seems neglectible against spending half the amount within the store, if you start with much money. For example, if the rules would be you're welcome with at least 2 dollars, need to always spend half your money, but pay no entrance or exit fee, you would only need 2^iterations dollars, to still have 2 dollars at the start of the Nth visit. Not almost three times as much money. That's the surprise of the resulting formula.

Reordering the steps, beginning in a shop, you have a certain amount there, divide it by two, then subtract 2 dollars, then again divide by 2, subtract 2. Until you have 1 left over to make the final exit. How would that compute? Instead of the sequence 3,9,21,45,93... you'd get a sequence 4,10,22,46,94... Does that help explain the 3?

Perhaps it's easier to see at each individual dollars sequence. The first ones are doubled more often than later dollars. You're summing up several powers of two sequences, each starting deferred.

The first dollar you "get" (if looking in reverse at the reversing of the last exit) is doubled N times, the second and third dollar you "get" are only doubled N-1 times etc. How would that look, if seperating the sequences for each of the dollars, perhaps noted this way:

1 -> 2 -> 4 -> 8 -> 16 -> 32
2 -> 4 -> 8 -> 16 -> 32
2 -> 4 -> 8 -> 16
2 -> 4 -> 8
2 -> 4
2
----------------------------
1 4 10 22 46 94

Those results are off by 1, but it shows the principple of summing up several sequences. Does it make things a bit clearer, perhaps?
[/hide]

Bye, Olaf.

 

[jges]

You get a couple bears on me next time we meet in person.

I hope for your sake they are of the koala and not the polar variety!

 

[vacunita]

sorry... beers.

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[karluk]

Olaf, I really like the way you systematically derived the formula by algebraic manipulation, rather than relying on a flash of inspiration to "see" what the formula ought to be. However, it seems to me that a far simpler way to arrive at the same conclusion is to redefine the problem a little and focus on the amount spent at each store, rather than the total amount needed to shop at n stores. Doing it this way, we see that the amount spent at each store is the sequence

3, 6, 12, 24, 48, ...

which is obviously in geometric progression. So, if I plan to shop at two stores, I will need to start with

$3 + $6 = $9

If I plan to shop at three stores, I will need

$3 + $6 + $12 = $21

and so forth. So this problem is actually asking us to calculate the sum of the first n terms of a geometric series. That's an exercise from high school algebra, and the formula provided by CajunCenturion and kwbMitel follows immediately.

 

[Olaf Doschke]

Ah, I see. That sequence of money spent in each shop is really simply growing by factor 2, starting with 3, and of course that 3 is easily seen.

I would have to dig deeper in memory about school math to remember the geomatric series, but yes, we had that lesson.

a*r^0+a*r^1+a*r^2+..., in that case a=3 and r=2 obviously.

And the general formula a(1-r^(n+1))/(1-r) yields 3*(1-2^(n+1))/(1-2) which can be simplified to 3*(2^(n+1)-1). If you begin with 0 instead of 3, then the formula simply results from that, true.

Bye, Olaf.