Mathematics desk
< March 16	<< Feb \| March \| Apr >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 17[edit]

Is zugzwang necessary to win Connect Four?[edit]

It is known that the first player always wins, but is zugzwang necessary? In other words, to win, is it necessary to reach a position such that any of the second player's possible moves allow a 4-in-a-row, but the first player would not win if it were their own move?--Jasper Deng (talk) 06:50, 17 March 2017 (UTC)[reply]

My first thought is no, Consider the following - = Empty, B= Blue, X=Red

-------
-------
-------
-------
------B
X---BBX
XXXBXBX

It is B's turn, and they drop the checker in Column 6 giving them two winning squares. Whichever column (6 or 7) X plays, B will play the other and win. no zugzwang.Naraht (talk) 18:01, 17 March 2017 (UTC)[reply]

@Naraht: But is this always true with any line of best play by the first player? In other words, is every position attainable by best play by the first player of the sort you describe?--Jasper Deng (talk) 18:53, 17 March 2017 (UTC)[reply]

I'm unclear as to what you are asking. Can Connect 4 be won by the first player putting your opponent in Zugzwang, yes. Can Connect 4 be won by the first player creating a fork, yes. Is your question whether both of these are possible if the first player does 'best play' or if both do 'best play'. According to the Connect Four article, player 1 starting in the middle allows the first player to force a win, player 1 starting in columns 1,2,6 or 7 allows the second player to force a win and in 3,5 a draw can be forced. No information as to whether any of those wins come from zugzwang or from forks.Naraht (talk) 19:00, 17 March 2017 (UTC)[reply]

My question is the latter: can the first player force a win with "double traps" alone, rather than also having to resort to zugzwang? In other words, does best play by the second player force the first to use zugzwang? A "double trap" is not just a fork - it refers to any situation where there are two simultaneous threats of connecting four, or a situation where parrying one threat to make four allows another.--Jasper Deng (talk) 19:18, 17 March 2017 (UTC)[reply]

No idea. It seems to me that your question comes down to whether if the ability to Pass is added to Connect 4, whether is still a first player win, would you agree with that?Naraht (talk) 19:21, 17 March 2017 (UTC)[reply]

Yes, that's one way you could phrase it, since zugzwang arises from the inability to pass.--Jasper Deng (talk) 19:22, 17 March 2017 (UTC)[reply]

I don't know. The article indicates that the first player can force a win on the 41st move or earlier. I'm not sure if there is any way to be sure that in the case where a game goes to the 41st move whether or not it is possible to prove from that that the move prior was forced. (OTOH, If connect four was a second player forced win with it being possible for the winning move to be move 42 then we would know, since either choice at 41 would lead to the win at move 42.)

Fixed points of functional nth roots[edit]

I recently discovered a theorem in a discussion with Soni (talk · contribs): if f is an nth functional root of g (whose domain and codomain are the same set, to allow the notion of a fixed point) and c is any fixed point of g, then for all k, f^k(c) is also a fixed point of g. Furthermore, the number of distinct points obtained by iterating f on c (that is, the numbers f^k(c) for all positive integers k) divides n.

My question concerns a related result: is it true that if x is a member of the preimage of some fixed point of g under g (e.g. g(x) = c), then x is also in the preimage under f of some (possibly different) fixed point of g? If g is restricted to having one fixed point, this seems to be true. Is it true in general?--Jasper Deng (talk) 06:57, 17 March 2017 (UTC)[reply]

I think this is a counterexample. Let g(x)=x^4 and f(x)=x^2 so that f(f(x))=g(x). Then the fixed points of g are S={0, 1, e^(nπi/3) : n=2,4}. Selecting c=1 then the pre-images of 1 under g are {i, -1, -i, 1}. But the pre-images of S under f are {0, 1, -1, e^(nπi/3) : n=1,2,4,5}. So i is a pre-image of 1 under g but is not a pre-image of any fixed point of g under f. Gandalf61 (talk) 11:57, 17 March 2017 (UTC)[reply]