Not Social Commentary
There's been some unfortunate flooding in Grid City:
The water swept in from the Northeast, so if any house is currently flooded, and it has neighbors to the North or East, it's a safe bet they're flooded too. (Other than this fact, and the grid layout, you should disregard the specifics of the map given.)
The water is low and flooded houses are still livable, but they need tap water. In a show of social cohesion befitting Grid City, each non-flooded household immediately donates 50 gallons of water to the effort. The goal is to distribute this water evenly among the flooded houses, and there is no shortage of volunteers to help. Also, quantities of water can be poured and combined or subdivided with precision.
But water is heavy and, let us say, has to be carried around on foot, so some plan is needed. An ideal of efficiency would be that water is never carried in the South or West directions.
Can both objectives be met simultaneously?
***
In the next post, I'll explain how this puzzle came up and my solution. But I'm curious to hear other approaches first, if you care to try.
The water swept in from the Northeast, so if any house is currently flooded, and it has neighbors to the North or East, it's a safe bet they're flooded too. (Other than this fact, and the grid layout, you should disregard the specifics of the map given.)
The water is low and flooded houses are still livable, but they need tap water. In a show of social cohesion befitting Grid City, each non-flooded household immediately donates 50 gallons of water to the effort. The goal is to distribute this water evenly among the flooded houses, and there is no shortage of volunteers to help. Also, quantities of water can be poured and combined or subdivided with precision.
But water is heavy and, let us say, has to be carried around on foot, so some plan is needed. An ideal of efficiency would be that water is never carried in the South or West directions.
Can both objectives be met simultaneously?
***
In the next post, I'll explain how this puzzle came up and my solution. But I'm curious to hear other approaches first, if you care to try.
Labels: puzzles
posted by Andy D at
10:45 PM
6 Comments:
I didn't understand how much the grid can be messed. My bet is that you can get any minimal solution and determine how much water moves between any pair (unflooded,flooded). The you can ask a volunteer for any pair to move water according to the shortest path (which is monotone).
Can be easily applied to not rectangular grids, given there is a "NORTH-EAST" path for any pair of houses.
By
Anonymous, at 6:43 AM
I don't agree with the last statement. Consider the northernmost unflooded and southernmost flooded houses. The water's path would be S-E.
Also, what is a 'minimal' solution?
By
Anonymous, at 10:38 AM
Hi Massimo,
I think I may have misunderstood your intended meaning.
Do you mean:
"Take an equitable allocation/delivery plan involving the minimal possible total legwork. Claim: all delivery paths are N-E monotone."
I think this may be true, but I'll need to mull it over. As hoped, it's a rather different approach from my own.
By
Anonymous, at 2:58 PM
Your approach also brings up a noteworthy point--that the notion of 'efficiency' I mentioned in the statement (as using only N/E steps)isn't really the most natural--but rather, the total 'gallon-blocks', i.e., the work done by volunteers carrying heavy water.
The work required can be lower-bounded by the difference in 'potential' between start and goal states, where the potential is defined as the sum (/integral), over each unit of tap water in the city, of the weight of that unit times its city-block distance from the N-E corner.
This is immediate, because each unit of carrying-work can lower the potential only by the same unit amount.
IF we can find an equitable allocation/delivery plan in which all steps are taken in the N and E directions, then the lower bound on work needed is *achieved*, since then each unit of work lowers the potential by the same amount.
So the 'N-E' notion of efficiency I requested in a solution is sufficient to yield a minimum-work equitable solution. This still begs the question of whether the N-E standard can actually be met.
If this doesn't make sense, please let me know.
By
Anonymous, at 3:16 PM
Oops. You're right I proved a minimum solution can be converted in a monotone one without increasing the cost. But monotone is weaker than NE.
Let me think a little bit more... 2AM on friday night is the perfect time for doing math in not native language :-D
By
Anonymous, at 8:34 PM
Order Generic Drugs Online. Order Generic Medication In own Pharmacy. Buy Pills Central.
[url=http://buypillscentral.com/buy-generic-brand-levitra-online.html]Discount Viagra, Cialis, Levitra, Tamiflu Pharmacy No prescription[/url]. Indian generic drugs. Discount drugs pharmacy
By
Anonymous, at 2:33 AM
Post a Comment
<< Home