Help with empty boxesalgorithmic problem.

[atwarwithmaths]

Hi, I've been given this problem for homework but I am completely baffled..I can't even translate the first move into values on the variables..

Any help on this would be greatly appreciated..Sorry if I'm being a bit abrupt here but my head is fried at this stage..

Thanks Guys..

Homework Statement

Eleven large empty boxes are placed on a table. An unknown number of the boxes is selected and, into each, eight medium boxes are placed. An unknown number of the medium boxes is selected and, into each, eight small boxes are placed.

At the end of this process there are 102 empty boxes. How many boxes are there in total?

Homework Equations

The Attempt at a Solution

Variables:
e = number of empty boxes
f = number of full boxes

Initial Values:
e=11
f=0

 

[Feldoh]

The maximum number of boxes total is 11*8*8 if we put 8 medium boxes into all 11 of the boxes then 8 small boxes into all of the medium boxes.

Notice the largest number of boxes disappear if we leave a large box empty.

The best way I could see to do it is semi-brute force. Basically taking out medium boxes until your empty boxes is less than 102. Then use the same method for the medium, and the small.

 

[atwarwithmaths]

Thanks for the quick reply Feldoh,

I like what you're saying..it makes sense but I have to come up with an invariant. If I don't then I will get no marks at all

 

[Dick]

Suppose you fill n boxes on the first step and m boxes on the second. Carefully count the number of empty boxes as a function of m and n. You'll find the number of empty boxes only depends on n+m. Since it equals 102, you can solve for n+m. Now, carefully count the total number of boxes. You'll find it also depends only on n+m. Not all choices of n and m give a solution, but those that do always give the same total number of boxes. I think.

 

[atwarwithmaths]

I think I may be getting it.. what variables would you introduce then?

n: number of boxes
e: number of empty boxes

I need to discover an invariant for this.

I've tried modelling a move: fill 1 box

e:= e+7
n:=n+8

what possible invariants can I get from this? TBH I'm not sure if I even understnad what an invariant is and this is due in tomorrow

 

[Dick]

n=number of large boxes filled. m=number of medium boxes filled. What's the TOTAL number of boxes (in terms of n and m)?

 

[atwarwithmaths]

n+m? I'm lost?

 

[Dick]

11 large boxes. n larges boxes filled, so 8*n medium boxes. m medium boxes filled, so 8*m small boxes. What's the total? Now count how many are empty. I'll get you started. 11-n large boxes are empty. How many medium boxes are empty and how many small boxes are empty? What's that total?