fun little problem

[galactus]

Here's a cute problem. Isn't too hard though. Just a recurrence.

Mary had a basket of hard-boiled eggs to sell. She sold half her eggs plus half an egg. Next she sold half her eggs and half an egg. The same thing occurred on her third, fourth and fifth times. When she finished, she had no eggs in her basket. How many did she have when she started?

Come up with the closed form recurrence relation and find the number of eggs she had initially.

 

[wjm11]

Mary had a basket of hard-boiled eggs to sell. She sold half her eggs plus half an egg. Next she sold half her eggs and half an egg. The same thing occurred on her third, fourth and fifth times. When she finished, she had no eggs in her basket. How many did she have when she started?

Come up with the closed form recurrence relation and find the number of eggs she had initially.

Is one of these what you are looking for?

Count down from 31 eggs to 0 eggs:

U1 = 31
Un = (Un-1)(.5) - .5
=> 31, 15, 7, 3, 1, 0 in 5 iterations

Count up from 0 to 31:

U1 = 0
Un = 2((Un-1) + .5)
=> 0, 1, 3, 7, 15, 31 in 5 iterations

 

[jonah]

A recurrence indeed. I’ve encountered this cute problem some years ago in a comic strip called SLYLOCK FOX by Bob Weber Jr. His version is as follows:

Super Challenge
A monkey had a basket of bananas. A customer approached him and purchased one-half of the bananas plus one-half of a banana. A second customer came and bought one-half of what he had left plus one-half a banana. A third customer purchased one-half of what was then left plus half a banana. After this sale the monkey had no bananas. He had not cut or broken a banana. How many did he have when he started?

Answer – Seven bananas.

The arithmetic behind the given answer seemed simple enough but coming up with an algebraic representation (or the so-called closed form recurrence relation) was apparently the super challenge. Tried to recreate the solution I came up with a few years ago but got stumped for about an hour. Finally gave up and blamed it all to an hour-long senior moment or disorientation. Good thing my records are all still intact. Apparently, here’s how my younger version did it:

x = number of hard-broiled eggs to sell.
a = number of hard-broiled eggs bought by 1st customer
b = number of hard-broiled eggs bought by 2nd customer
c = number of hard-broiled eggs bought by 3rd customer
d = number of hard-broiled eggs bought by 4th customer
e = number of hard-broiled eggs bought by 5th customer

We then have the equation

x – a – b – c – d – e = 0

where

\(\displaystyle a = {\textstyle{1 \over 2}}x + {\textstyle{1 \over 2}} = {\textstyle{1 \over 2}}\left( {x + 1} \right)\)

\(\displaystyle b = {\textstyle{1 \over 2}}\left( {x - a} \right) + {\textstyle{1 \over 2}}\)

\(\displaystyle c = {\textstyle{1 \over 2}}\left( {x - a - b} \right) + {\textstyle{1 \over 2}}\)

\(\displaystyle d = {\textstyle{1 \over 2}}\left( {x - a - b - c} \right) + {\textstyle{1 \over 2}}\)

\(\displaystyle e = {\textstyle{1 \over 2}}\left( {x - a - b - c - d} \right) + {\textstyle{1 \over 2}}\)

which then boils down to

\(\displaystyle x - a - b - c - d - e = 0 \Leftrightarrow x = 31\)

 

[galactus]

Very good. I thought it was an old chestnut.

The closed form is \(\displaystyle a_{n}=32(\frac{1}{2})^{n}-1\)

 

[galactus]

Here's another old walnut you may like and probably have seen. It is a little tougher than the other I reckon. It may involve a little number theory; viz, the Chinese Remainder Theorem.

An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Have a go if you wish

 

[galactus]

No one wanted to try the last eggs problem. With the remainders mentioned it is obviously a 'mod' problem.

This is, no doubt, an oldie because it mentions a horse stepping on the cart. Probably goes back to Gauss's time .

But here is how I approached it. I know a little number theory, but I am not as knowledgeable as I would like. I can get around a little mod arithmetic though.

Everything gives remainders of 1 except for 7, which has remainder 0.

\(\displaystyle x\equiv 1(mod \;\ 2)\)

\(\displaystyle x\equiv 1(mod \;\ 3)\)

\(\displaystyle x\equiv 1(mod \;\ 4)\)

\(\displaystyle x\equiv 1(mod \;\ 5)\)

\(\displaystyle x\equiv 1(mod \;\ 6)\)

\(\displaystyle x\equiv 0(mod 7)\)

We can add up the top 5 and get \(\displaystyle x\equiv 1(mod 60)\). Because 60 is the LCD of 2,3,4,5,6

Therefore, \(\displaystyle x=60s+1\)

Sub this into the last one:

\(\displaystyle 60s+1\equiv 0(mod \;\ 7)\Rightarrow 60s\equiv -1(mod \;\ 7)\Rightarrow 4s\equiv 6(mod \;\ 7)\Rightarrow 2s\equiv 3(mod \;\ 7)\)

Now, from \(\displaystyle 2s\equiv 3(mod \;\ 7)\), we get \(\displaystyle \frac{2s-3}{7}=x\). This must be an integer and that first occurs when s=5.

So, \(\displaystyle x=60(5)+1=\fbox{301}\)

She had 301 eggs, most likely anyway.