3
$\begingroup$

This is original problem:

You have n number of envelopes, and $100$ $\$1$ bills. you have to put these bills in the envelopes in such a way that any amount between $1$ to $100$ can be reached just by combining the envelopes without counting amount inside it. You can however, write the number of bills on top of the envelopes. How many envelopes will you require and how much amount is there in each of those envelopes. (The goal is to use minimum number of envelopes)

A lot of us here have seen this problem. So many of us already know the solution. I am not posting the solution because I don't want to spoil the fun for those who haven't.

There exist only one feasible solution to this problem given that the restriction applies, that you cannot change the bills inside the envelopes.

I gave this problem to a candidate in an interview today. He gave me a solution which I never thought of.

He said, we use $26$ envelopes and put a prime number of $\$1$ bills in each one of it. So we have envelopes having $2,3,5,7,11,13,17,19,\dots$ number of $\$1$ bills and one envelope having $1$ count in it.

EDIT 2: If it is allowed to interchange the bills inside the envelopes then this solution is perfectly true as well. For Eg. $52 = 47 + 3+2$.

$54=53+1$

$55=53+2$,

$56=53+3$;

and so on.

If I generalize it, I can say Every number between $1$ and $100$ can be represented as a sum of prime numbers(max $3$) or sum of prime numbers and $1$ (if at all $1$ is not considered a primes number). And it is perfectly valid.

I extended this further, and I realized I can reach to any number between $1$ to $1060$ (the sum of all prime numbers between $1$ and $100$) provided the prime number is used only once.

EDIT: the sum is corrected to $1060$. I counted some extra numbers which were not prime sorry.

for example, $500=97+93+89+87+83+47+3+1$

My question is : How far is it true? Is there a point where this will fail? what happens when we extend the envelopes to have prime numbers between $1$ and $200$, does it increases the ability to count. Is it a well know theorem, series anything? Some one must have thought about it previously.

$\endgroup$
14
  • 1
    $\begingroup$ But if you can not count the inside, how do you know what amount is within the envelope? In that case only one solution is possible IMHO. $\endgroup$
    – mvw
    Commented Jul 25, 2014 at 11:48
  • 3
    $\begingroup$ 51 is not a prime. But I think you are rediscovering Goldbach's conjectures, which see. $\endgroup$ Commented Jul 25, 2014 at 11:57
  • 1
    $\begingroup$ With $100\$$ you can only fit the 9 smallest primes so how can he use 26 envelopes in his solution?! The sum of the $26$ smallest primes is $>1000$. $\endgroup$
    – Winther
    Commented Jul 25, 2014 at 12:05
  • 1
    $\begingroup$ @Sid Wither's objection is that you only have $100$ dollars to begin with. You don't have enough money to fill the $26$ envelopes. $\endgroup$ Commented Jul 25, 2014 at 12:23
  • 1
    $\begingroup$ Another interesting variation is to put a square number of one dollar bills in every envelope. You just need at most four envelopes to pay any integer amount: this is the Lagrange four squares theorem. Welcome into the field of additive number theory :) $\endgroup$ Commented Jul 25, 2014 at 12:56

0

You must log in to answer this question.

Browse other questions tagged .