9
$\begingroup$

8 white and 8 black dots are drawn on a piece of paper. Parcly and Tori take turns drawing edges, always between white and black dots not already adjacent (so the graph is always bipartite); the first player to complete a 4-cycle (square) loses.

If Parcly starts first, who has a winning strategy and how is it executed?

This puzzle is an offshoot of my (now deep) research into Zarankiewicz's problem that sprang from my genies' chess puzzles, the results of which (maximal graphs, proofs and supporting code) are being added to my Kyoto repository and the relevant OEIS sequences. My SAT-based approach to the problem is also the subject of my honours project at the National University of Singapore.

Improve this question
$\endgroup$
1
  • $\begingroup$ Can you please post the answer ? $\endgroup$
    – Hemant Agarwal
    Commented Oct 20, 2022 at 15:14

1 Answer 1

Reset to default
2
$\begingroup$

Second Player will always :

Win.

Winning Strategy + Reason + Explanation :

It seems that this is Zarankiewicz Problem.
Posed like this for our Puzzle:
What is the number Z(N;M) of edges in a BiPartite Graph having N nodes on each side & not having a Complete MxM Subgraph ?
Here N=8 & M=2;
According to Paper "Bipartite Ramsey numbers and Zarankiewicz numbers" [[ Wayne Goddard & Michael A.Henning & Ortrud R.Oellermann ]] this is exactly 24, which is enough to solve the Puzzle.
Every time P makes a move and T makes a move, 2 edges are consumed out of the Initial 24; Eventually, after 12+12=24 moves, P will have no edges to make a move and will have to make a Square and lose.

Comment:
With 4 Dots on each side, the Winner will be the Other Player.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I do not think this actually works – 4-cycles don't have to use white/black vertices in the same positions on both sides. $\endgroup$
    – Parcly Taxel
    Commented Jan 23, 2022 at 20:04
  • 1
    $\begingroup$ WLOG, after Parcly connects W1-B1, Tori's first move is either W1-B2 or W2-B2. All other options are equivalent to one of these. $\endgroup$
    – Daniel Mathias
    Commented Jan 23, 2022 at 20:49
  • 2
    $\begingroup$ Also, regarding gender: both Parcly and Tori are female genies. $\endgroup$
    – Parcly Taxel
    Commented Jan 24, 2022 at 15:47
  • 1
    $\begingroup$ I don't see how you have proved the strategy. As far as I can see, what you've stated shows that if both players cooperate, the longest possible game is 25 moves. But what if either player plays a move not in that 24-edge graph at some earlier point in the game? There are after all 64 edges to choose from. Maybe this forces a shorter game, and gives a shorter winning strategy for one of the players? $\endgroup$
    – Jaap Scherphuis
    Commented Jan 25, 2022 at 16:40
  • 2
    $\begingroup$ @JaapScherphuis I worked out the strategy with 3 white and 3 black dots; Parcly wins by making a 5-edge tree (paths of length 2, 2, 1 starting from a central vertex), despite the maximal number of edges without making a 4-cycle being 6. $\endgroup$
    – Parcly Taxel
    Commented Jan 25, 2022 at 19:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.