Author |
Topic: Voronoi Game/Puzzle (Read 1055 times) |
|
BMAD
Junior Member
Posts: 57
|
 |
Voronoi Game/Puzzle
« on: May 23rd, 2014, 6:12am » |
 Quote  Modify
|
You and an opponent are sharing a regular sheet of paper. You will play an area game. Your opponent goes first and marks a single point in the center of the paper. You will make a mark in a different location and then it is their turn, your turn and so on. The game continues until you each have four points on the paper. As this is the "Voronoi Game", the paper is then divided into 8 areas. An area is created by drawing perpendicular lines between the nearest points until enough perpendicular lines define the area (ensuring that the border defines area that is closest to that receptive point). Is there a strategy that you can utilize to ensure you have the largest total area at the end of the game?
In summary:
The points uniquely determine the lines, which give the size of each point's cell.
Cells that surround each point comprise the points closer to it than to any other point.
The strategy comes in placing your points.
|
| « Last Edit: May 23rd, 2014, 6:13am by BMAD » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2874
|
|
Re: Voronoi Game/Puzzle
« Reply #1 on: May 23rd, 2014, 9:03am » |
Quote Modify
|
So you score all the area that's closer to one of your points than to one of the opponent's?
|
|
IP Logged |
|
|
|
BMAD
Junior Member
Posts: 57
|
|
Re: Voronoi Game/Puzzle
« Reply #2 on: May 23rd, 2014, 9:10am » |
Quote Modify
|
yes.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Voronoi Game/Puzzle
« Reply #3 on: May 23rd, 2014, 9:23am » |
Quote Modify
|
I first thought the 2nd player must win since he has more choice in the 1st move and plays all his moves knowing his opponent's move.
But this reasoning should apply also if each player plays 1 point. And it fails.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Voronoi Game/Puzzle
« Reply #4 on: May 23rd, 2014, 9:59am » |
Quote Modify
|
But I think 2nd player can win the game by dividing the paper in 4 smaller rectangles and playing the 4 centers (or very close).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Voronoi Game/Puzzle
« Reply #5 on: May 23rd, 2014, 12:17pm » |
Quote Modify
|
Maybe the way to look at it is that player one picks the point and player two picks a dividing line through it. Player two can pick his point arbitrarily close and at any side of player one's point; so if he does, that's what it comes down to in the limit. In particular, player two can pick which side of the line is his, and so can always pick the better side of the area divided by the line, if there is one (which there isn't for N=1).
|
| « Last Edit: May 23rd, 2014, 12:18pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BMAD
Junior Member
Posts: 57
|
|
Re: Voronoi Game/Puzzle
« Reply #6 on: May 23rd, 2014, 2:49pm » |
Quote Modify
|
But player 1's third move also determines a dividing line
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Voronoi Game/Puzzle
« Reply #7 on: May 24th, 2014, 12:35am » |
Quote Modify
|
Player 1's move only determines the point the line has to go through. (Bearing in mind that I'm mapping the original problem to one that's equivalent for a subset of possible solutions.) So in that approach player 1 chooses a Voronoi cell, and player 2 divides it in two and picks a half.
Actually, that's probably not the right approach for looking at it, because the Voronoi cell player 1 chooses will change the previous existing ones, so he'd pick one that takes area from player two and then player two would get only around half back using this approach. So this is not a good strategy.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print