A puzzle:
A box contains an unknown number of pebbles, each marked either X, Y or Z. You do not know the exact numbers of X, Y, and Zs, but you know that number of X > Z > Y. You must now sort them into groups with the following conditions:
- Each group must not have more than 8 members.
- Each group must contain at least 2 Ys.
- Each group must contain at least 1, but not more than 3 Xs.
- Each group must contain at least 1, but not more then 3 Zs.
Are there situations when it is not possible ensure that all pebbles in the box in groups that satisfy all the above conditions?
If each group must contain 2 Ys, the maximum number of groups that can be formed is Y/2.
If each group cannot contain more than 3 Xs or 3 Zs, the minimum number of groups that has to be formed is the bigger set (i.e. X) divided by 3, X/3
Therefore, if X/3 > Y/2, the pebbles cannot be grouped in a way that satisfies all conditions!
This very intriguing and random puzzle came from our staff contact time, where we were told to basically form groups according to the above conditions. Intuitively, I felt certain that there would be situations where we simply cannot group ourselves to ensure that all groups fulfil the above conditions. However, I couldn’t quite prove it there and then (and anyway it was not important to because nothing detrimental was going to happen if we didn’t quite adhere to the conditions anyway). Nevertheless, I was mulling over it for a couple of days and during our Sunday brunch, Ning and I figured it out!
What is more interesting, though, is in looking at the problem as a system level problem. If you start off with all pebbles in the box and you are merely grouping them, then as long as X/3 ≤ Y/2, the problem can be solved with all groups meeting the conditions.
However, if you change the problem such that each pebble becomes an agent capable of moving to another group, and all the pebbles are already in random piles, even when it is possible that the groupings are not achieved when X/3 ≤ Y/2.
Let’s postulate a very simple and reasonable principle each agent would work by: each agent will attempt to move as little as possible in trying to be in a group that meets the conditions.
In the worst case scenario, there are some groups of agents among other random groups where there are 6 Ys, 1X, and 1Z. These groups would satisfy the conditions, and hence none of the agents, crucially the Ys, would move. As Y dictates the maximum number of groups, if all of the groups containing Ys contain 6 Ys, the maximum number of groups is further reduced from Y/2 to Y/6. Since both X>Y and Z>Y, there will be leftover Xs and Zs. In other words, this will not be an optimal distribution of the pebbles.
How can we then ensure the optimal distribution of agents? We can then put in another operating principle in the agents to require them to move when there is another group where Y < 2 even if they are already in a group which does not fails the conditions. However, if we do not assume that each agent is omniscient of all the groupings in the system, then we need to ensure that there is communication between groups of agents.
On the other hand, we can tweak the conditions such that the limiting factors are exactly distributed i.e. Y = 2 instead of Y ≥ 2. However, this will reduce the flexibility of distribution.
What if we return to the initial conditions and ask, what do the conditions represent? In a real world, we might postulate that conditions represent some sort of baseline functioning conditions i.e. the local systems (groups) would not work if the conditions are not met. However, these may not represent the local optimal functioning conditions.
Anyway! I’m not an optimization expert but it was a very interesting experience deriving these from an innocuous staff conference instruction. If I had another life, I’ll be an academic!
