INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

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

y = 3 * (2x - 1)

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-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

By my usual method of manually working out solutions and looking for patterns it looks like the following formula will work

Hidden:

(2^interations - 1) times 3 = Dollars required

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

RE: Progressive Spending

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

Hidden:


To start the induction, we need to show that

y = 3 * (2x - 1)

gives the correct amount when x=1. But 3 * (21 - 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 * (2x - 1)

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

y = 3 * (2x-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 * (2x - 1) - 1
= 3 * 2x - 4

dollars remaining.

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

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

dollars remaining

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

(3 * 2x-1 - 2) - 1
= 3 * 2x-1 - 3
= 3 * (2x-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

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

RE: Progressive Spending

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

Hidden:

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?

Bye, Olaf.

RE: Progressive Spending

Quote (vacunita)

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!

RE: Progressive Spending

(OP)
sorry... beers. cheers

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

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.

RE: Progressive Spending

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.


Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Resources

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close