Minimum number of trips for a truck with weight limit of $200$ to transport boxes with weights 81, 73, 67, 49, 37, 34, 30, and 26

Question

My 9-year-old son had the following math problem to solve:

A truck can carry $200$kg or less. We have 8 different boxes with given weights:

$81$kg, $73$kg, $67$kg, $49$kg, $37$kg, $34$kg, $30$kg, and $26$kg

What is the minimum number of trip required to move all boxes from city A to city B.

I looked at it for 5 minutes and couldn't figure out a meaningful approach other than brute force.

I was in front of my computer and quickly wrote a MATLAB script to bruteforce it.

The solution was 2 trips: one with boxes $81$, $49$, and $67$; and the other with boxes $73$, $37$, $30$, $26$, and $34$.

Is there an obvious way, or at least one more clever than brute force, to solve that kind of problem?

Here, it's not that hard because we only have 8 boxes. But what about a similar problem with a bigger set? Can we only rely on brute force?

Bonus question:

What is this supposed to teach to a 9yo kid ?

Answer 1

Perhaps the main lesson would be:

The greedy approach is not always optimal

What would be the greedy method? Pack the truck with heaviest boxes first until you cannot add any more boxes. This results in a first tour with 81+73+37=191 and a second tour with 67+49+34+30=180 and then a final tour with the one remaining 26 kg. The fact that the 26 kg just barely fail to fit into the second tour are perhaps intended to annoy you and make you play around to somehow achieve two tours.

• Replacing the 37 of tour with something smaller? There is no way to get four boxes with 81+73 as already 26+30 is too much.
• Replace the 73 with something smaller? doing so and continuing greedily, we arrive at 81+67+49=197 and the rest on the second tour - and done!

Given the age, however, I suppose this problem would be more appropriate if the trial-and-error phase could be performed physically (e.g., moving around suitable paper cutouts). But the numbers used in this problem do not seem to allow that easily.

Answer 2

Not an answer!

Just too long for a comment, and I wanted OP and other parents to know what is the right attitude.

As a teacher/father:

• I strongly advice to NOT help your sons/daughters;
• NEVER belittle children assignments/homework.

We assign problems/readings to our students not to their families.

Most important:

making unnecessary arguments with teachers harms students and hinders healthy and serene teamwork

Answer 3

A math-talented high school student can avoid brute force by keying on the comment of Dietrich Burde, and then looking for a first try that involves a group of numbers whose sum is congruent to 0, mod 10.

Within this approach, a plausible first "sub-try" is identifying pairs of numbers whose sum is congruent to 0, mod 10. Doing this, one gets lucky in observing the two pairs (73,67) and (34,26), since 140 + 60 = 200.

It is unclear whether the problem was designed to allow luck, versus replacing (67,26) with [for example] (68,25).