Split Vote
A team of 58 prospectors 
has just recovered a number of identical gold nuggets equal to the answer to last week’s Talking Midpoints problem. They decide upon the following scheme to divide up their treasure. The oldest prospector will propose a plan for how many nuggets each gets; nuggets cannot be divided or discarded. Then all 58 of the prospectors will vote on the plan. If the plan gets at least two more yes votes than no votes, the treasure will be divided according to plan, and the prospectors will all go their separate ways. If it does not, the oldest prospector is ejected from the team and from the International Prospector’s Union, and the process repeats with the 57 remaining prospectors, with the now-oldest prospector proposing a new plan, to be ratified with at least two more yes votes than no, or rejected otherwise, and so on.
The prospectors will always act in their own self-interest according to the following priorities: (1) No prospector wants to be ejected from the Union; (2) Every prospector wants to maximize his share of the treasure; (3) Every prospector considers the certainty of a given number of nuggets now to be superior to any chance, less than certainty, of the same number of nuggets later; and (4) all else being equal, every prospector prefers to have less competition by trying to ensure that as many prospectors as possible are ejected from the Union. The priority order of these goals means, for example, that a prospector will never forego a larger share of the treasure for the sake of having an additional team member ejected from the Union.
Is there a plan that the oldest prospector can propose that will prevent his ejection from the International Prospector’s Union? If so, what is the largest number of nuggets the oldest prospector can keep in such a plan?
Treasure Trek
Prospector Pete has buried three gold nuggets within a one mile by one mile plot of land. In an effort to slow down and foil thieves, Pete selected locations for the three nuggets to maximize the total distance one has to walk to dig up all three nuggets, starting from the first nugget chosen and ending when the last nugget is reached.
How far would you be forced to walk to dig up all three of Prospector Pete’s nuggets?
Solution to Week 29
Patriotic Packing. Since the glass height and the box height match and the glasses must be upright, this is really a two-dimensional problem of packing circles into a rectangle. Also, to simplify the numbers slightly, notice that we can divide everything by two: the problem is the same as packing unit-diameter circles into a six-by-eight rectangle. It is tempting therefore to think of placing the circles in a square grid pattern, for a total of 48 circles fitting in the rectangle. On the other hand, it is well known that the overall most efficient packing of circles in the plane is in a hexagonal grid, so we need to check how many circles can fit in the rectangle in a hexagonal grid pattern. Imagine an infinite hexagonal grid of unit-diameter circles; how can a six-by-eight rectangle be placed thereon to maximize the number of circles in the rectangle? First, note that we can assume that at least one circle must be tangent to a side of the rectangle — if not, consider the circle that comes closest to a side without being tangent to it, and slide the rectangle toward the center of that circle until it becomes tangent. No formerly whole circles are cut off, because if so, they would have been closer to a side. So all that might possibly happen is that a previously partial circle may have become whole. In any case, the number of circles does not decrease. Similarly, we can assume that at least one side is tangent to more than one circle, because we can rotate the rectangle by the smallest increment that makes one side tangent to two circles. Again, this can’t cut off any formerly whole circles, so the number of circles in the rectangle is no fewer after the rotation.
Now it is a matter of trying different configurations in which some side is tangent to at least two circles in a hexagonal packing. A little playing around will make it clear that there are only two orientations that are contenders for packing the most circles — one in which the long side of the rectangle lines up along a row of circles, and one in which the short side of the rectangle lines up along a row of circles. In the former case, we get three rows of 8 circles plus three rows of 7 circles, or 45 circles, into the rectangle — not as good as the square grid. But in the latter case, we get five rows of 6 circles plus four rows of 5 circles for a total of 50 circles, i.e., glasses that the team can pack in a box. (To verify that all 9 rows can fit in the box this way, note that the centers of the rows are the height of a unit equilateral triangle apart, i.e., √3/2, and there is one extra unit of space between the centers of the circles and the walls, and that 1 + 4√3 < 8.)
Sometimes problem writers like to put in a sneaky backdoor hint. In this case, the best packing for the glasses is the same arrangement as the stars on the American flag! Incidentally, since the flag used a square grid arrangement of the stars back when there were 48 states, this problem shows that you can use equally large stars for 50 states as you could for 48 states.
There may be one other thing bothering you. How do we really know that 50 is the greatest number of glasses that can fit? After all, there seems to be wasted space at the two ends of the rows that have only five circles. If we could just consolidate some of that space… Because of the overwhelming optimality of the hexagonal close packing for the plane as a whole, and how well a six-by-eight rectangle meshes with that packing, it’s considered extremely unlikely that any irregular packing could squeeze in a 51st glass (or in other words, we’ll have to make the stars slightly smaller if the United States ever gets a 51st state). But on the other hand, to the best of my knowledge, nobody has ever rigorously proved that it’s impossible to fit in a 51st circle. It’s amazing how easily mathematics can take us to the realm of unsolved mysteries!
Recent Weeks
Week 28: Closing Times & Midpoint Well Taken, solution to Fancy Dice
Week 27: Fancy Dice & Gothic Arc, solution to HIJKMNOP
Week 26: HIJKMNOP & Inscribed Square, solutions to Time to Burn & Durable Digits
Week 25: Time to Burn & Durable Digits, solutions to Noticing Numbers I & Noticing Numbers II
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.
