Open problems - Revision history

Selinger: Better sectioning; added some context

2025-03-15T16:11:58Z

Better sectioning; added some context

Demer: showed that a generalization is false

2025-03-15T12:13:56Z

showed that a generalization is false

Selinger: Moved seventh row template problem to "formerly open" problems.

2023-11-09T02:14:40Z

Moved seventh row template problem to "formerly open" problems.

Selinger: Added category

2023-10-01T03:11:39Z

Added category

Selinger: /* Formerly open problems */ Added a refutation for the height-8 template candidate.

2022-08-18T00:17:11Z

‎Formerly open problems: Added a refutation for the height-8 template candidate.

Selinger: typos

2021-10-05T22:03:53Z

typos

Selinger: typos

2021-10-05T19:55:29Z

typos

Selinger: Added an old question from LG forum.

2021-10-04T14:12:25Z

Added an old question from LG forum.

Selinger: Fixed links, added problems, moved solved problems to separate section.

2021-10-04T02:14:50Z

Fixed links, added problems, moved solved problems to separate section.

Selinger: Edited categories

2020-12-28T21:25:35Z

Edited categories

@@ Line 1: / Line 1: @@
 * Are there cells other than a1 and b1 which are theoretically losing first moves?
@@ Line 11: / Line 13: @@
 * Is the following true? Assume one player is in a winning position (will win with [[optimal play]]) and the opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move is winning, even [[passing]] the turn. (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].)
-:*The generalization of the above statement to monotone set-coloring games is false, as shown in section  1.4 .
+:*The generalization of the above statement to monotone set-coloring games is false, as shown in [[#Failure_for_maker-breaker_games|section 3]] below.
 == Formerly open problems ==
@@ Line 97: / Line 99: @@
 '''Answer:''' Yes. See [[Seventh row edge templates]].
-=== Failure for monotone set-coloring games ===
+== Failure for maker-breaker games ==
 I give two examples.  The first is simple and highly-symmetric.    The second goes 3-of-3:  There are exactly 3 legal moves outside the set, and all 3 of them win.
@@ Line 103: / Line 111: @@
 simple and highly-symmetric:
-Take a hexagonal [https://en.wikipedia.org/wiki/Bipyramid bipyramid], and give each equatorial edge an arrow pointing to a pole, such that the directions of the arrows alternate.  Consider the [https://en.wikipedia.org/wiki/Maker-Breaker_game Maker-Breaker game] on the vertices of the resulting object, where the winning sets are the vertices of faces such that the equatorial edge's arrow points to the face's polar vertex.
+Take a hexagonal [https://en.wikipedia.org/wiki/Bipyramid bipyramid], and give each equatorial edge an arrow pointing to a pole, such that the directions of the arrows alternate.  Consider the maker-breaker game on the vertices of the resulting object, where the winning sets are the vertices of faces such that the equatorial edge's arrow points to the face's polar vertex.
 Breaker is in a winning position:        No matter what Maker's first move is, Breaker's first move is a pole.  (If Maker's was not a pole, then there is symmetry between the poles until Breaker chooses one.)    If neither of Maker's first two moves was a pole, then Breaker's second move is the other pole, winning for Breaker.    Otherwise, Breaker pretends Maker's pole move was Maker's first move, and wins by [[Pairing_strategy|pairing]] using the equatorial edges whose arrows point to the pole Maker played.
@@ Line 113: / Line 121: @@
 going three-of-three:
-This one is a [https://en.wikipedia.org/wiki/Maker-Breaker_game Maker-Breaker game] whose underlying set is {0,1L,1R,2L,2R,3L,3R,4}.  There are exactly 6 minimal winning sets, and they are {0,1L,2L},{2L,3L,3R},{2L,3L,4} and the three formed by interchanging L with R.
+This one is a maker-breaker game whose underlying set is {0,1L,1R,2L,2R,3L,3R,4}.  There are exactly 6 minimal winning sets, and they are {0,1L,2L},{2L,3L,3R},{2L,3L,4} and the three formed by interchanging L with R.
 Breaker is in a winning position:    By symmetry, assume Maker does not play a R element.  0 and 2L each [[Dominated_cell#Switch-domination|switch-dominate]] 1L, so this leaves 0,2L,3L,4 as candidates for Maker's first move.  If Maker's first move is 3L or 4, then Breaker can play 2L and win with the [[Pairing_strategy|pairing]] {0,1R},{2R,3R}.  If Maker's first move is 2L or 0, then Breaker wins by playing any of 3L,3R,4 and using the [[Pairing_strategy|pairs]] {0,1L} and {1R,2R} and whichever of {3L,3R,4} Breaker hasn't yet played.

@@ Line 11: / Line 11: @@
 * Is the following true? Assume one player is in a winning position (will win with [[optimal play]]) and the opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move is winning, even [[passing]] the turn. (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].)
 == Formerly open problems ==
@@ Line 95: / Line 96: @@
 '''Answer:''' Yes. See [[Seventh row edge templates]].
 [[category: Open problems]]
 [[category: Forums]]

@@ Line 4: / Line 4: @@
 * Conversely, is it true that, for example, c3 is a winning first move on every Hex board of size at least 5?
 * Is the [[center opening|center hex]] on every Hex board of [[Board_size|odd size]] a winning opening move?
@@ Line 92: / Line 90: @@
    contents="R i1 g3 e5 c7 a9"/>
 [[category: Open problems]]
 [[category: Forums]]

← Older revision		Revision as of 03:11, 1 October 2023
Line 95:		Line 95:

	[[category: Open problems]]		[[category: Open problems]]
		+	[[category: Forums]]

@@ Line 16: / Line 16: @@
 == Formerly open problems ==
-* [[Sixth row template problem]]: Does there exist an [[edge template]] which guarantees a secure [[connection]] for a [[piece]] on the sixth row?<br> '''Answer:''' Yes, [[edge template VI1a]] is such a template.
+=== [[Sixth row template problem]] ===
-* Are the templates below valid in their generalization to larger sizes?  (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].) <br> <hexboard size="1x1"
+Does there exist an [[edge template]] which guarantees a secure [[connection]] for a [[piece]] on the sixth row?
    float="inline"
    edges="bottom"
@@ Line 32: / Line 40: @@
    coords="none"
    visible="area(c1,a3,c3)"
-   contents="R c1 c3"/><hexboard size="4x4"
+   contents="R c1 a3"/><hexboard size="4x4"
    float="inline"
    edges="bottom"
    coords="none"
    visible="area(d1,a4,d4)"
-   contents="R d1 d3"/><hexboard size="5x5"
+   contents="R d1 b3"/><hexboard size="5x5"
    float="inline"
    edges="bottom"
    coords="none"
    visible="area(e1,a5,e5)"
-   contents="R e1 e3 e5"/><hexboard size="6x6"
+   contents="R e1 c3 a5"/><hexboard size="6x6"
    float="inline"
    edges="bottom"
    coords="none"
    visible="area(f1,a6,f6)"
-   contents="R f1 f3 f5"/> <br> '''Answer:''' No. The first one in the sequence that is not connected is the one of height 8. Instead, it requires this much space: <br> <hexboard size="8x9"
+   contents="R f1 d3 b5"/>
   float="inline"
    edges="bottom"
    coords="none"
-   visible="area(i1,d6,c6,a8,i8)"
+   visible="area(h1,a8,h8)"
-   contents="R i1 i3 i5 i7"/><br>The corresponding template of height 9 requires this much space:<br><hexboard size="9x11"
+  contents="R h1 f3 d5 b7 c7,a8--e8"/>
   float="inline"
    edges="bottom"
    coords="none"
-   visible="area(k1,g5,c7,a9,k9)"
+   visible="area(h1,a8,i8,i6)"
-   contents="R k1 k3 k5 k7 k9"/>
+  contents="R h1 f3 d5 b7"/>
 [[category: Open problems]]

← Older revision		Revision as of 19:55, 5 October 2021
Line 11:		Line 11:
	* On boards of all [[board size\|sizes]], is every opening move on the [[Board#Diagonals\|short diagonal]] winning?		* On boards of all [[board size\|sizes]], is every opening move on the [[Board#Diagonals\|short diagonal]] winning?

−	* Is the following true? Assume one player is in a winning position (will win with [[optimal play]]) and opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move ~~are~~ winning, even [[passing]] the turn. (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].)	+	* Is the following true? Assume one player is in a winning position (will win with [[optimal play]]) and the opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move is winning, even [[passing]] the turn. (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].)

@@ Line 12: / Line 12: @@
 * Is the following true? Assume one player is in a winning position (will win with [[optimal play]]) and opponent plays in a hex X. Let the set A consist of all empty hexes that are members of any path between opponents edges that uses the stone at X. If A is non-empty, A contains a winning move. Otherwise any move are winning, even [[passing]] the turn. (This problem was posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].)
 == Formerly open problems ==
-* [[Sixth row template problem]]: Does there exist an [[edge template]] which guarantees a secure [[connection]] for a [[piece]] on the sixth row? The answer is yes, and [[edge template VI1a]] is such a template.
+* [[Sixth row template problem]]: Does there exist an [[edge template]] which guarantees a secure [[connection]] for a [[piece]] on the sixth row?<br> '''Answer:''' Yes, and [[edge template VI1a]] is such a template.
 [[category: Open problems]]

← Older revision		Revision as of 21:25, 28 December 2020
Line 11:		Line 11:
	* Two further open problems are posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].		* Two further open problems are posed by [[Jory]] in the [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=167 Little Golem forum].

−	[[category:~~Theory~~]]	+	[[category: Open problems]]