Project 2: Ice Cream

There's a flavor of Ben and Jerry's ice cream called ``Everything but the ...'' that includes almonds, peanut butter cups, white-chocolate chunks, and toffee pieces among a mix of vanilla and chocolate ice cream. While everybody likes ice cream, many people like some parts more than others. Personally, I prefer vanilla ice cream to chocolate, and I particularly like white chocolate. My daughter Sam (who came up with the idea that led to this project) prefers chocolate ice cream, on the other hand.

When a large container of this ice cream is shared among a family, there is room for both competition and collaboration. People will compete for the bits that everybody likes, but if two people have complementary preferences they might cooperate. For example, if Bob likes almonds, he might take a serve of ice cream that is strategically selected to include many almonds. That might expose a new layer of ice cream with toffee pieces that Alice particularly likes, so Bob hands the container to Alice when he's done.

The Reliable Ice-Cream Company makes a family-sized ice cream container that is 24cm long by 15cm wide by 8cm high. We'll model the container as a grid of cells, each cell being a cube of side length 1cm. A cell can contain one of F flavors, corresponding to either a special ingredient (e.g., a nut) or a base flavor (e.g., vanilla ice cream). The Reliable Ice-Cream Company is reliable because they guarantee a fixed and equal number of cells of each flavor, and advertise those numbers on the container label. So if you haven't seen any almonds yet, they're waiting in the lower layers! The ice cream is randomly ``shuffled'' so that each cell has the same independent probability of being occupied by a certain flavor. The Reliable Ice Cream Company manufactures nine kinds of ice cream, one for each of the following values of F: {2,3,4,5,6,8,9,10,12}.

The ice cream is shared among a family of p people in the following manner: A person, say Alice, is chosen randomly to go first. Alice serves herself some ice cream according to the procedure described below. Then Alice chooses who in the family to pass the ice cream container to next, say Bob. Bob then serves himself, and chooses another family member, and so on. Every family member gets to receive the container exactly $\lfloor \frac{120}{p} \rfloor$ times, and is allowed to take up to 24 units of ice cream each time. When passing the ice cream around, you cannot pass the container to somebody who has already had h helpings if there are family members who have received fewer than h helpings.

To help yourself to ice cream, you employ a 2cmx2cm ``spoon''. This spoon can be placed anywhere in the container that is aligned with the grid boundaries, and will serve you from the topmost 1cm layer that sits below the spoon. In a new ice cream container, that will always be 4 cells of ice cream from the topmost layer. In a partially consumed container, the spoon might (a) get less than 4 cells from the topmost layer because some cells have already been taken; or alternatively (b) take ice cream from a lower layer that has been exposed because all of the cells above have been cleared. Note that a layer does not have to be cleared completely to access lower layers; only the region vertically above the selected region needs to have been cleared.

You will be able to see straight down, meaning that as part of a layer of the ice cream is cleared away on each spoonful, the distribution of flavors underneath becomes known. You can take as many spoonfuls as needed while you have the ice cream, subject to the constraints above. You don't see the state of the ice cream until you receive the container. However, you do get incremental updates as you remove each spoonful, and you see the updated contents of each family member's bowl at the end of their turn.

Your preferences are determined by a random permutation $f_1,\ldots,f_F$ of the F flavors. So f₁ is your favorite flavor, and f_F is your least favorite flavor. You want to have lots of f₁, and little of f_F, if possible. Your individual score S will be calculated as

$$\sum_{i=1..F} (F-i+1)*\mbox{count}(f_i)$$

where a bigger score is better. The term count(f) is the number of cells of flavor f you have accumulated. Since you're a family and want each other to enjoy their ice cream too, your final score also depends on a group score G defined as the average of the individual scores of all the other family members. Your final score is (S+G)/2.

You don't know the permutations of the other family members, but you do get to see what they put in their bowls, so you can make an educated guess.