Question 1029555
Cakes cost $8 each and pies cost $6 each. How many combinations 
of cakes and pies can you purchase for between $72 and $120, 
inclusive?
<pre>
Let x = the number of cakes and y = the number of pies.
x and y must be non-negative integers.  A "lattice point" 
is a point both of whose coordinates are integers, in this 
case only non-negative integers.  The inequality is

{{{"$72"<="$8"x+"$6"y<="$120"}}}

Or, dividing through by $2,

{{{36<=4x+3y<=60}}}

We graph the set of inequalities: {{{system(4x+3y>=36,4x+3y<=60)}}} 

{{{drawing(339600/1099,400,-.99,15.99,-.99,20.99, 
green(rectangle(0,0,15,20),rectangle(0,0,9,12)),
locate(.4,20.8,A), locate(.4,12.8,B), locate(.4,1,O),
locate(9.3,1,C), locate(15.3,1,D), locate(15.3,20.8,E),
locate(9.3,12.8,F),graph(339600/1099,400,-.99,15.99,-.99,20.99), line(9,0,0,12),
line(15,0,0,20) )}}}

The solution set is the number of lattice points interior to
or on the sides of trapezoid ABCD.

Notice that the line 4x+3y=36, which is AD and the line 
4x+3y=60 which is BC are the respective diagonals of the 
rectangles AODE and BOCF in the figure
 
{{{(matrix(8,1,
The,number, of, lattice,points,matrix(1,3,in,or,on),trapezoid,ABCD))}}}{{{""=""}}}

{{{(matrix(12,1,
The,number, of, lattice,points,with,non-negative,non-diagonal,coordinates,below,diagonal,AD))}}}{{{""-""}}}

{{{(matrix(11,1,
The,number, of, lattice,points,with,non-negative,coordinates,below,diagonal,BC))}}}{{{""+""}}}

{{{(matrix(12,1,
The,number, of, lattice,points,with,non-negative,coordinates,on,the,diagonals,matrix(1,3,AD,and,BC) ))}}}{{{""=""}}}

We first find the number of lattice points on the
two diagonals BC and AD 

We find the points on 
diagonal BC
The equation of BC is 
{{{4x+3y = 36}}}
Write 4x as 3x+x
{{{3x+x+3y=36}}}
Divide through by 3
{{{x+x/3+y=12}}}
Isolate the fraction term
{{{x/3=12-x-y}}}
The right side is a non-negative integer,
therefore so is the left side.  Let that
integer by p, then
{{{x/3=p}}}
{{{x=3p}}}
{{{12-x-y=p}}}
{{{12-3p-y=p}}}
{{{12-4p=y}}}
So the diagonal lattice points on AD are 
(3p,12-4p) where p = 0,1,2,3
Thus there are 4 lattice points on diagonal BC

We find the number of lattice points on diagonal
AD:
The equation of AD is 
{{{4x+3y = 60}}}
Write 4x as 3x+x
{{{3x+x+3y=60}}}
Divide through by 3
{{{x+x/3+y=20}}}
Isolate the fraction term
{{{x/3=20-x-y}}}
The right side is a non-negative integer,
therefore so is the left side.  Let that
integer by q, then
{{{x/3=q}}}
{{{x=3q}}}
{{{20-x-y=q}}}
{{{20-3p-y=q}}}
{{{20-4q=y}}}

So the lattice points on AD are (3p,20-4q) 
where q = 0,1,2,3,4,5

Thus there are 6 lattice points on diagonal AD.

Next we find the number of lattice points with 
non-negative coordinates below the line BC.
There are 10x13 = 130 lattice points in or on
the rectangle BOCF.  That's because the lattice
points on OC go from 0 through 9, which is 10
lattice points. Also, the lattice points go from 
0 through 12 on OB, which is 13 lattice points
along the left side.

By symmetry, there are the same number of lattice 
points in rectangle BOCF above the diagonal of AD,
as there are below it.

The number of lattice points in or on rectangle 
AODE above or below but not on diagonal AD is 130-4=126.
So there are 126/2 = 63 latice points below AD.

Next we find the number of lattice points with 
non-negative coordinates below the line AD.
There are 16x21 = 336 lattice points in or on
the rectangle AODE.  That's because the lattice
points on OD go from 0 through 15, which is 16,
and from 0 through 20 on AO, which is 21.
By symmetry. there are the same number of lattice 
points above the diagonal AD in rectangle AODE, 
as there are below it.

The number of lattice points in or on rectangle 
AODE above or below the diagonal AD is 336-6=330.
So there are 330/2 = 165 lattice pointsin rectangle
AODE below AD. 

However we want only the non-diagonal lattice points 
and the 165 includes the 4 diagonal points on BC.  So
we must subtract those 4 from the 165, which leaves
161 non-diagonal points below AD. 

So we substitute in
 
{{{(matrix(8,1,
The,number, of, lattice,points,matrix(1,3,in,or,on),trapezoid,ABCD))}}}{{{""=""}}}

{{{(matrix(12,1,
The,number, of, lattice,points,with,non-negative,non-diagonal,coordinates,below,diagonal,AD))}}}{{{""-""}}}

{{{(matrix(11,1,
The,number, of, lattice,points,with,non-negative,coordinates,below,diagonal,BC))}}}{{{""+""}}}

{{{(matrix(12,1,
The,number, of, lattice,points,with,non-negative,coordinates,on,the,diagonals,matrix(1,3,AD,and,BC) ))}}}{{{""=""}}}{{{161-63+10}}}{{{""=""}}}{{{108}}}

Answer: {{{108}}}

Edwin</pre>