In class we saw that if McNuggets came in boxes of size 4 and 7, then it is impo

Question

In class we saw that if McNuggets came in boxes of size 4 and 7, then it is impossible to get 17 McNuggets, but for any n greaterthanorequalto 18, we can get exactly n McNuggets. Define g(a_1, a_2) = the largest number of McNuggets that cannot be obtained for boxes of size a_1 and a_2. So, g(4, 7) = 17. Implement two different well known algorithms to compute g(a_1, a_2, a_3) or g(a_1, a_2, a_3, a_4). Well known algorithms include those developed by Rodseth, Davison, Killingberlro, Scarf and Shallcross, Heap and Lynn, Greenberg, Nijenhuis, Wilf and Kannan.

Explanation / Answer

g(a,b) = ab - a - b

g(4,7) = 4*7 - 4 - 7 = 17

for g(a,b,c) where a<b<c,

Rodseth's algorithm assumes that the numbers a<b<ca<b<c are pairwise relatively prime. There is a result due to Johnson that helps in dealing with other cases -- by defining f(a,b,c)=g(a,b,c)+a+b+cf(a,b,c)=g(a,b,c)+a+b+c, it can be shown that f(da,db,c)=df(a,b,c)f(da,db,c)=df(a,b,c), when aa and bb are relatively prime.

I will illustrate the algorithm with a "generic example". First, recall that any rational number, like 197197, can be expanded as a finite continued fraction, and intermediate truncations give better and better approximations to the original rational number.

So 197197 is 2+1x2+1x, where xx is 1+1y1+1y, and so on. Successive truncation yields the sequence 21,31,8321,31,83 and 197197 itself. This is called the sequence of convergents, though I will call themdextroconvergents, with a nod to organic chemistry.

I could also define levoconvergents. 197197 is 31x31x, where xx is 412412. This gives the sequence 31,11431,114 and 197197. Note that levoconvergents are monotone decreasing, unlike dextroconvergents which alternately underestimate and overestimate the number in question.

Now suppose you want to compute g(19,29,89)g(19,29,89). First, find the unique positive integer s<19s<19 such that 29s89(mod19)29s89(mod19). It turns out that s=7s=7.

Starting from 11, take the sequence of numerators of levoconvergents to as=197as=197, to get 1,3,11,191,3,11,19.

Also, 19mod7=2;7mod2=1;2mod1=019mod7=2;7mod2=1;2mod1=0. Take the sequence of moduli, ending with 00, to get 7,2,1,07,2,1,0.

Putting these together, we get an increasing sequence
0=019<111<23<71=s0=019<111<23<71=s

Determine the two consecutive terms between which cb=8929cb=8929 lies. (Observe that the definition of ss ensures that s>c/bs>c/b.) Clearly,

TU=23<cb=8929<VW=71TU=23<cb=8929<VW=71

Now, f(a,b,c)=bV+cUmin(bT,cW)=412.f(a,b,c)=bV+cUmin(bT,cW)=412.

g(a,b,c)=f(a,b,c)abc=275.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.