Oreo Placement Game – OPG
Every week Steve and Tanya meet for coffee and play a game in the coffee shop with the Oreos they brought. They take turns placing those Oreos on a napkin that lies on the table before them. While they do that Oreos must not overlap. Also Oreos must stay within the napkin’s boundary: Overflow is forbidden. The player who places the last Oreo wins the game.
- Two players take turns and place one Oreo each time on a napkin.
- Napkin has a circle shape.
- Oreos can’t overlap.
- Oreos can’t overflow the boundary of the napkin.
- Winner is the player who puts down the final Oreo.
Is there a winning algorithm/strategy for either of the players?
Yes, there is an algorithm Steve and Tanya can use in order to win at OPG. But this algorithm works only for the player who puts down the first Oreo.
- Be the player who starts the game.
- Place your Oreo at the center of the napkin in the first move.
- For the rest of the game wherever your opponent places his/her Oreo, play your next move with taking its symmetry by the center Oreo.
- Eventually second player will run out of space on the napkin.
Place it to the center.
Wherever your opponent places his/her Oreo, rotate that location 180 degrees and place your Oreo there.
Continue the same strategy. Eventually your opponent will run out of space and you will win.
In OPG, you can use the same algorithm with a napkin that has a regular polygonal shape. But first player might need adjustments in certain situations. Assume that you play OPG in a triangular-shaped napkin.
If you can fit even number of Oreos on the napkin, placing the first Oreo on the center of the triangle will be a losing strategy:
When the first Oreo placed on the center and exactly four Oreos fit inside the triangle, you will not win no matter what.
In order to avoid that you must place the first oreo slightly above the center:
Placing the first Oreo slightly above the center will divide the rest of the triangle into two isolated spaces where you can fit one Oreo each. First player will win no matter what happens with this strategy.
For pentagonal napkins you will have to use the same strategy which you used for triangular napkins:
It is possible to fit 6 Oreos on this pentagon. If you start first and place your Oreo on center, you will lose.
However, when you place the first Oreo slightly closer to one of the corners, algorithm will guarantee a win in every single time.
Q: Is there a winning algorithm in OPG when you don’t get to start the game?
Yes, there is. But in order to accomplish that second player must select a shape that is not convex. Let’s say the napkin is shaped as follows:
Here, first player tries to place his/her Oreo such that the triangle will be divided into two isolated places. No matter what the second player does, first player will win.
Second player must decide the shape of the napkin like following:
In these situations winner should leave the napkin in two isolated regions such that these regions must have space for only one Oreo. Thus, second player must play his/her second to last move in such way:
No matter where the first player places his/her Oreo, second player will win if he/she leaves two isolated areas on the napkin.
Would the same algorithm work if Oreos were in squared shapes? Test this with napkins that are in triangular and pentagonal shapes.
M. Serkan Kalaycıoğlu