Too much money!!!!!!! Please help!

Printable View

April 20th 2006, 04:54 AM
Slipknotfanatic89

Too much money!!!!!!! Please help!

In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?
April 20th 2006, 11:37 AM
topsquark

Quote:

Originally Posted by Slipknotfanatic89

In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?

There is no upper limit on the price. Any possible price in whole dollars will be of the form: $6*n + $11*m where n and m are non-negative integers. There are an infinite number of prices that don't fit this requirement.

-Dan
April 20th 2006, 09:49 PM
CaptainBlack

Quote:

Originally Posted by topsquark

There is no upper limit on the price. Any possible price in whole dollars will be of the form: $6*n + $11*m where n and m are non-negative integers. There are an infinite number of prices that don't fit this requirement.

-Dan

Not so, when I get the chance I will post the proof that there is always
a maximum price which cannot be made with bills of denominations $b1 and
$b2 where b1 and b2 are co-prime.

RonL
April 21st 2006, 02:15 AM
CaptainBlack

Quote:

Originally Posted by Slipknotfanatic89

In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?

This is not as clear as I would like and there is probably a more elegant way
to do this, but here it is anyway:

Consider a whole number of dollars $\$N$ .

Now consider

$ R(k)=N-k.6,\ k \in \{0,\ \dots,\ 11 \} $

Now as $11$ and $6$ are co-prime, for each
$r \in \{0,\ \dots,\ 11 \}$ :

$ R(k) \equiv r \mod 11,\ \mbox{for some }k \in \{0,\ \dots,\ 11 \} $

So there exists $\rho$ and $\kappa \ge 0$ such that:

$ N=\rho.11+\kappa.6 $ ,

moreover if $N \ge 11 \times 6$ , $\rho \ge 0$ .

Hence if $N \ge \$ 66$ it can be made up by a combination of
$\$ 11$ and $\$ 6$ bills.

Now trail and error show that $\$65=1\times \$11+9\times \$6$ , but that there is no such representation for $N = \$64$ .

So $\$64$ is the largest whole number of dollars which could not be the price of an item sold in this country

RonL
April 21st 2006, 04:56 AM
topsquark

Huh! Well, I guess you DO learn something new every day! :) Sorry about that, Slipknotfanatic89!

-Dan
April 21st 2006, 05:20 AM
c_323_h

wow, CaptainBlack, you're good , i thought it was infinite too
April 22nd 2006, 05:08 PM
ThePerfectHacker

Quote:

Originally Posted by SlipKnotfanatic89

In a country whose currency consists of $6 bills and $11 bills, the price of every item sold is a whole number of dollars that can be be paid (exactly) using these two types of bills. What is the largest whole number of dollars which could not be the price of an item sold in this country?

Mathematically what you are trying to find the smallest $n$ such as you cannot find non-negative integers $x,y$ such as,
$6x+11y=n$ .
-----
This problem is from number theory. It uses something called linear diophantine equation (Bezout's Identity):
If $ax+by=c$ and $d|c$ where $d=\gcd(a,b)$ then this diophantine equation has solutions.
If $x_0,y_0$ is a solution pair, then all solutions and every solution (if and only if) are:
$\left\{ \begin{array}{c}x=x_0+\frac{b}{d}t\\y=y_0-\frac{a}{d}t \end{array} \right$ .
-----
Notice that,
$6(2)+11(-1)=1$ multiply by $n$ to get,
$6(2n)+11(-n)=n$ , by the theory of linear diophantine equations you have that all and every solution is,
$\left\{ \begin{array}{c}x=2n+11t\\ y=-n-6t \end{array} \right$ for an integer $t$ .
But you want whole numbers for $x,y$ thus,
$x\geq 0 \mbox{ and }y\geq 0$
Thus,
$2n+11t\geq 0\mbox{ and }-n-6t\geq 0$
Solving these inequalites we find that $t$ must satisfy,
$-\frac{2n}{11}\leq t\leq -\frac{n}{6}$
Placing a common denominator (and removing the negative),
$\frac{11n}{66}\leq -t\leq \frac{12n}{66}$
Thus,
$11n\leq k\leq 12n$ where $k=-66t$ is also an integer.
The only requirements that $k$ must have is to be a multiple of 66.
All the integers that satisfy this inequality are,
$S=\{11n,11n+1,11n+2,...,11n+(n-1),12n\}$
Thus, given this set we need to find the largest $n$ such as there is no multiple of 66.
In total we have $n$ distinct integers in increasing order. Thus, if $n\geq 66$ then by the Pigeonhole Principle we have that there must be a multiple of 66.
Instead of approaching this problem theoretically simply do trail and error beginning with $n=65$ , soon we will see that $n=49$ contains no mutiples of 66.
-----
Wow two mistakes in a row first topsquark, CaptainBlack. Hope I am not the next one,
$64=6(7)+11(2)$ .
April 23rd 2006, 12:01 AM
CaptainBlack

Quote:

Originally Posted by ThePerfectHacker

Wow two mistakes in a row first topsquark, CaptainBlack. Hope I am not the next one,
$64=6(7)+11(2)$ .

Must have been something wrong with my caluclator yesterday.
It probably needs an oil change :mad:

RonL
April 23rd 2006, 06:28 AM
ThePerfectHacker

My calculator is a turing machine.

I use my computers calculator:
C:\WINDOWS\system32\calc.exe
it hs 34 digits.

I was thinking of downloading a super advanced calculator with more than 100 digits.
April 23rd 2006, 07:50 AM
CaptainBlack

Quote:

Originally Posted by ThePerfectHacker

My calculator is a turing machine.

I use my computers calculator:
C:\WINDOWS\system32\calc.exe
it hs 34 digits.

I was thinking of downloading a super advanced calculator with more than 100 digits.

For arbitrary precision work I use a CAS, though I have been thinking
about using UBASIC for some number theory calculations recently (it
works with 2000+ :D digits).

RonL
April 23rd 2006, 08:38 AM
rgep

This is Sylvester's Coin Problem, also known as the Frobenius Coin Problem. Sylvester showed that the largest sum that cannot be made using coins of values a and b (where a and b are coprime) is $(a-1)(b-1)-1 = ab - a -b$ .

There are articles in Wikipedia and MathWorld.

In the specific case of coins of value 6 and 11, note that 50 can be made up as 4.11 + 1.6 and then 51=3.11+3.6, 52=2.11+5.6, 53 = 1.11 + 7.6, 54 = 0.11 + 9.6, 55=5.11 + 0.6, 56 = 4.11 + 2.6 and the pattern repeats with an interval of 6.
April 23rd 2006, 08:56 AM
ThePerfectHacker

Quote:

Originally Posted by rgep

This is Sylvester's Coin Problem, also known as the Frobenius Coin Problem. Sylvester showed that the largest sum that cannot be made using coins of values a and b (where a and b are coprime) is $(a-1)(b-1)-1 = ab - a -b$ .

There are articles in Wikipedia and MathWorld.

In the specific case of coins of value 6 and 11, note that 50 can be made up as 4.11 + 1.6 and then 51=3.11+3.6, 52=2.11+5.6, 53 = 1.11 + 7.6, 54 = 0.11 + 9.6, 55=5.11 + 0.6, 56 = 4.11 + 2.6 and the pattern repeats with an interval of 6.

It looks interesting. I was able to demonstrate that $n\geq ab$ (where a and b are co-prime) can always be expressed. But I was not able to demonstrate the second propstition, I just used trail and error.
-----
Does it generalize as if,
$\gcd(a_1,a_2,....a_n)=1$
Then, $\prod^n_{k=1}a_k-\sum^n_{k=1}a_k$
Is the largest non expressable number?
April 24th 2006, 04:02 PM
Slipknotfanatic89

The largest number I have found thus far is 49 by 11(-1) + 6(10). I can't remember whose formula this follows, but it is the lagest number I have found that cannot be solved using 6 and 11
April 24th 2006, 05:29 PM
ThePerfectHacker

Quote:

Originally Posted by Slipknotfanatic89

The largest number I have found thus far is 49 by 11(-1) + 6(10). I can't remember whose formula this follows, but it is the lagest number I have found that cannot be solved using 6 and 11

In the previous posts CaptainBlack and I give two different solutions to this problem (CaptainBlack was wrong because

Quote:

my calculator needs an oil change

). Then, rgep made another interesting post that this is a theorem. Anyways yes, the largest non-expressable number is 49. Notice that important fact that $\gcd(6,11)=1$ otherwise it is impossible.

Let me explain let, $\gcd(a,b)=d>1$
Then there are no integral solutions to the equation,
$ax+by=c$ where $d\not |c$ because than the left hand side is divisible by $d$ while the right hand side is not. But when the $d=1$ then it is possible because all numbers are divisible by one.