From 360: Shinju, a geometrical game. You're given an arrangement of shells in some of the squares of a square grid. One of the shells hides a pearl. Your goal is to find it, opening at most four shells. When you open a shell, it either contains the pearl, or a number. That number is the distance to the pearl, in the (T)chebyshev distance.
There's a nice little result hiding here:
Problem 1: Given any arrangement of shells, prove that it is possible to find the shell in four clicks.
Since you always get four clicks (at least as long as I played), the game becomes trivial if you can find a constructive proof of that fact. (If you're the sort of person that likes to rack up points in video games, though, I think you get more points if you don't use all your clicks -- so how do you set things up so that you're likely to solve the puzzle in less than four clicks?)
Problem 2: Generalize (to higher dimensions, different metrics, etc.)
Subscribe to:
Post Comments (Atom)
7 comments:
Problem 1: pick a shell that's on the orthogonal hull (i.e nothing to left or above it). The answer induces two orthogonal lines where the pearl can lie.
If we know which of the two lines we are on, it takes at most two clicks. Pick an extreme point, and the offset uniquely defines the location.
However, finding this line takes one click (pick a point furthest from the intersection of the two lines).
Total: 1 + 1 + 2 = 4.
For higher dimensional variants: the first click defines d (d-1)-facets. Selecting which one to recurse on takes d-1 clicks (extreme points in each facet). This defines the recurrence
T(d) = 1 + d-1 + T(d-1)
T(1) = 2
T(d) is d(d+1)/2 + 1.
This could probably be optimized slightly, by also querying the corner opposite the first query, but the asymptotics would remain the same, I think.
I'd hazard that a similar result holds for L_1, but I'm not terribly sure.
Finding the pearl is akin to drawing geometric circles. Pick a shell, and (assuming you didn't find the pearl) draw a circle of the given distance centered on that shell.
Pick any shell on that circle. If it's not a match, you draw a second circle with the new distance.
Now you have two circles, with two points of intersection. The pearl is in one or the other, so you need no more than four shells opened.
suresh: I can easily draw examples that have no such point as the one you suggest starting with.
marty: in the l^\infty norm there can be many points of intersection of two circles. Be careful!
unapologetic: not sure what you mean. to be more precise:
take the top most occupied row of the grid. In that row, take the left most point.
Suresh: choosing that point may induce more than two lines.
More to the point, let's examine exactly what was said:
pick a shell that's on the orthogonal hull (i.e nothing to left or above it)
But now let's assume the upper-left corner is unoccupied, but there are shells in both the left column and top row. Now the way you're saying to pick the point might leave something to the left of it, against your conditions from before.
I'm not saying you're wrong in the general idea, but you have to be more careful in how you specify things.
To clarify suresh's idea:
Take a point in the top row. Now what you have left is a U-shaped path of potential spots.
Now choose the topmost point on the left branch, or if it's empty take the leftmost point on the bottom, or if that's empty take the bottommost point on the right.
Now worst case you have a line segment; take one endpoint of that line segment, and you're done.
The last bit is a little handwavy but I think it's easy enough to fill in the details. The key is that the U isn't square but has a bottom that's at least twice as wide as the verticals. So when you choose the point on the U, it's not equidistant from points on two sides, and once you measure that distance you get points on just one side of the U.
Post a Comment