Ecco is faced with an agrarian geometry puzzle this month.

May 01, 2005
URL:http://www.drdobbs.com/parallel/optimal-farming/184406090

Dennis is a professor of computer science at New York University. His most recent books are Dr. Ecco's Cyberpuzzles (2002) and Puzzling Adventures (2005), both published by W.W. Norton. He can be contacted at [email protected].

Solution to Last Month's Dr. Ecco

Michael Sturm handed Ecco his business card. The listed profession: Geometer-Farmer. "I'm a rather unusual farmer," he said after noting Ecco's smile. "My passions in fact are geometry and mechanics. I have designed sprinklers that can move around a radius of up to 1.5 kilometers for example. The farmer part is familial. My brother and I have just bought a rectangular property that is 1 kilometer north-south by 2 kilometers east-west.

"We want to water all of our land without watering too much area twice and without watering outside our rectangles. So, we measure cost (or overhead, if you wish) as the area outside the square that receives water and the area within the square having more than one sprinkler circle covering it. We want to minimize cost while ensuring that every bit of our farm is watered."

Liane interrupted briefly: "So if some area gets hit by three sprinklers, then you count that the same as if it were hit by just two?"

"Yes, good question," said Sturm shaking Liane's hand. "Not everyone picks up that subtle point. Now here are my questions. For k=5:

1. What is the radius of k circles that will cover the entire rectangle while minimizing cost?
2. Answer the same question if all the sprinkler radiuses must be the same."

Sturm went on, but Tyler and Liane could not solve the next questions. So these are still open:

1. How do your answers change as k increases, say, to 10, 20, and 100?
2. For a given k, what is the rectangle whose aspect ratio would be best and that would allow one to cover the rectangle at minimum cost?

Reader Solutions To "Dig That!"

Michael Birken and Rick Kaye came up with several very clever solutions to the "Dig That!" puzzle (DDJ, February 2005).

The problem was to find the route of an underground tunnel using probes at the intersection of a road grid. Each probe could determine the entering and leaving directions of the tunnel if the tunnel were present. Mike's five-probe solution for a tunnel of length 8 is available at http://cs.nyu.edu/cs/faculty/shasha/papers/digthat8.PNG. For tunnels of lengths 10 and 12, he came up with 8 and 15 probe solutions, though he is not sure of optimality.

DDJ

Figure 1.

Solution to Last Month's Dr. Ecco

Solution to "Jam Session," DDJ, April 2005.

1. We represent the 6 data bits followed by 4 check bits as follows:
b1 b2 b3 b4 b5 b6 c1 c2 c3 c4
Here is one possibility of what the check bits could do:
c1 is odd parity on b1, b2, b3, b4, b5, b6, c1, c4
c2 is odd parity on b1, b2, b3, b4, c3, c2
c3 is odd parity on b1, b2, c1, c3, c4
c4 is odd parity on b1, b5, b4, c4
The trick is to locate the parity tests that don't work if any bit has been flipped and to make sure these are all different. If all the parities are correct, then no single bit has been flipped. If there is an error in b1, then the parities corresponding to c1, c2, c3, and c4 will all be bad.
Error in b2, then c1, c2, and c3 will be bad.
b3: c1, c2.
b4: c1, c2, c4.
b5: c1, c4.
b6: c1
c1: c1, c3
c2: c2
c3: c2, c3
c4: c3, c4.

2. If you know the offset between the bit flip to the first receiver and to the second is an odd number, then you can use:
b1, b2, b3, b4, b5, b6, b7, b8, Podd, Peven
where Podd ensures that there are an odd number of 1s among b1, b3, b5, b7, Podd and Peven ensures that there are an odd number of 1s among b2, b4, b6, b8, and Peven. Here is why this works: If no error is detected, then the data bits are correct. If the first receiver detects an error, say for Podd, then the second can detect an error only for Peven because of the odd offset. Therefore, one of the two receivers will receive an error-free Podd group and and an error-free Peven group.

3. If you know the offset is 4 bits, then Ivan Rezanka showed how 3 check bits are enough. First note that with an offset of 4, the bits that could flip are bit 1 for the first receiver and bit 5 for the second—denoted (1,5)—or (2,6), (3,7), (4,8), (5,9), (6, 10), (7,1), (8,2), (9,3), or (10,4).
Here is a three check bit solution:
b1 b2 b3 b4 b5 b6 b7 c1 c2 c3
c1 is odd parity on b1, b4, b6, b7
c2 is odd parity on b2, b4, b5, b7
c3 is odd parity on b3, b4, b5, b6
If all parity bits check out for either receiver, we are done. If some pair changes, we detect as follows: If bit 1 to the first receiver and bit 5 to the second is flipped then c1 for the first receiver and c2 for the second will be incorrect. We denote this by (c1, c2). Note that when merging these two signals, the reconstructor must recognize this ordering. So, we abbreviate this first situation as follows:
(1,5) -- (c1, c2, and c3)
and continue as follows:
(2,6) -- (c2, c1 and c3)
(3,7) -- (c3, c1 and c2)
(4,8) -- (c1 and c2 and c3, c1)
(5,9) -- (c2 and c3, c2)
(6,10) -- (c3, c3)
(7,1) -- (c1 and c2, c1)
(8,2) -- (c1, c2)
(9,3) -- (c2, c3)
(10,4) -- (c3, c1 and c2 and c3)
Note that each diagnostic is different.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.