16
$\begingroup$

Yin-Yang is a grid deduction puzzle with the following rules:

  • Fill each cell with either a black circle or a white circle.
  • All circles of a given color must form a single orthogonally-connected region.
  • Every 2x2 area must contain circles of both colors.

I have a Yin-Yang generator which randomly generates completely filled grids satisfying the rules above; it selects them uniformly from all filled grids (of the requested size) which satisfy the rules. It can only generate 10x10, 15x15, and 20x20 grids.

Occasionally, the generator produces a grid in which all border cells are the same color. If I want to maximize the chance of it randomly generating such a grid, should I ask it to generate a 10x10 grid, a 15x15 grid, or a 20x20 grid?

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you know some clever argument that allows one to answer this with pen and paper or is this essentially a request to compute all possible grids on a computer and then just compare the numbers? $\endgroup$
    – quarague
    Commented Jul 24 at 15:08
  • 3
    $\begingroup$ @quarague Definitely the former. $\endgroup$
    – Sneftel
    Commented Jul 24 at 15:26
  • 1
    $\begingroup$ Closely related: A problem about Yin-Yang puzzles, whose solution uses the same idea for its proof. $\endgroup$
    – Bubbler
    Commented Jul 25 at 1:23
  • $\begingroup$ I spend a few minutes looking and counting a 5x5 grid and thought, this is no fun for bigger grids with pen and paper but there is no need for that. Nice puzzle. $\endgroup$
    – quarague
    Commented Jul 25 at 6:40

1 Answer 1

Reset to default
13
$\begingroup$

15x15. The 10x10 and 20x20 cannot have a solid border.

Proof. Give a checkboard coloring to the interior vertices of the grid. Consider the border separating the white cells from black cells. This will be a single path that goes through all the interior vertices (IVs) and only the IVs. (It goes through all by the "each 2x2 has both colors", only those because the outer border is a single color, and there's a single circuit by the "single orthogonal region" rule.) Vertices will alternate between the colors, and it forms a loop, so it has an even length. 10x10 grid has 81 IVs and 20x20 has 361 IVs, both odd, so they can't be done.

  XXXXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  X.XXXXXXXXXXXXX
  X.............X
  XXXXXXXXXXXXXXX

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Nice argument! Given that a significant portion of the audience here is new to both the puzzle type and graph theory, maybe spend another spoiler block to demonstrate why all those nodes must be visited? $\endgroup$
    – Bass
    Commented Jul 24 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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