## Progressive Spending

## Progressive Spending

(OP)

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.

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

## RE: Progressive Spending

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:

## Hidden:

^{x}- 1)--------------

Good Luck

To get the most from your Tek-Tips experience, please readFAQ181-2886: How can I maximize my chances of getting an answer?

Wise men speak because they have something to say, fools because they have to say something. - Plato## RE: Progressive Spending

## Hidden:

^{interations}- 1) times 3 = Dollars required**********************************************

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

## RE: Progressive Spending

## Hidden:

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}- 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}- 4dollars remaining.

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

(3 * 2

^{x}- 4) / 2= 3 * 2

^{x-1}- 2dollars 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.

## RE: Progressive Spending

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

## RE: Progressive Spending

## Hidden:

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?

Bye, Olaf.

## RE: Progressive Spending

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

## RE: Progressive Spending

----------------------------------

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

## RE: Progressive Spending

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.

## RE: Progressive Spending

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.