# Tag Info

26

Call the number of days until expiration the "freshness" of the cookie. A cookie with freshness $1$ is here (and can be eaten) today, but will be gone tomorrow; a cookie with freshness $n+1$ will have freshness $n$ tomorrow. If all the cookies' freshnesses have the same parity, then this will persist for the entire game: one player (Eve) will only see ...

23

Methods Starting from the base url http://www.cross-tables.com/annotated.php?a=1 I used a combination of Python's urllib, multiprocessing and BeautifulSoup to extract the first 10000 games. The games were parsed and turned into numpy 15x15 Boolean matrices. The matrices were then turned into graphs making an edge if two adjacent cells in the matrix were ...

18

In 3-dimensional chess, it is possible to force checkmate starting with a finite number of rooks. As this fact still appears to be open, I'll post a method of forcing checkmate with 96 rooks, even though it should be clear that this is not optimal. You can remove some of the rooks from the method I'll give below, but I am aiming for a simple explanation of ...

10

There are several standard texts. You may want to start with a short essay, "The History of Combinatorial Game Theory", by Richard J. Nowakowski. The paper lists the main texts you may want to consult. For a more exhaustive list of references, see "Combinatorial games: Selected bibliography with a succinct GourmetIntroduction", by Aviezri Fraenkel. Thomas ...

8

It turns out that the maximum possible diameter uses the full hundred tiles! My friend Carl illustrated this in 2008 in a game he made up, here: http://www.cross-tables.com/annotated.php?u=2493#0# . Thanks for the question!

8

This is known as Wythoff's game. The losing positions are $(\lfloor n \varphi\rfloor, \lfloor n \varphi^2\rfloor)$ where $\varphi$ is the golden ratio. An interesting way of presenting this game is to have the players move a Queen on a chessboard, which you can find at cut-the-knot here.

7

There is some discussion of this topic at the very end of the second edition (2000) On Numbers and Games by Conway. He describes work by himself, Simon Norton, and Martin Kruskal to define integration. According to the description, it looked good for a while, producing workable logarithm function in terms of the integral of $x^{-1}$, but then got stuck, and ...

7

Here's one option of a type you didn't suggest. Take any symmetric game. Modify the game as follows: After the first player's first move, give the second player the option to continue the game as usual, or to switch places, taking the first player's position and giving the (former) first player the next move as second player. Assuming that ties are ...

6

You can do it generically. Treat the case of the multiplier separately. So there's 11C5 (eleven choose 5) ways with no multiplier. You want the average. It's just 5 times the average of those eleven numbers. Then there's 11C4 ways with the multiplier. Let the multiplier be k. The average for the other 4 will be 4 times the average of the eleven. So, if A's ...

6

Astoundingly enough, this has already been studied. And I'm almost embarrassed to say that I'm familiar with the result. I used to freecell a lot. And FYI, 11982 is the impossible Frecell game. But I recommend entering in games -1, -2, -3, etc too. So here are some stats from some studies of freecell. Firstly, the depth of the aces, i.e. how many cards ...

6

The minimum number of switches required is $100$. This puzzle can be turned into a linear algebra problem over ${\Bbb Z}/2{\Bbb Z}$ by letting the vector $v\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which switches are pressed ($1$ if pressed, $0$ if not), the vector $w\in({\Bbb Z}/2{\Bbb Z})^{100}$ record which lights are initially on ($1$ if on, $0$ if off), ...

6

This PDF might be a useful starting point. It also mentions a book Fair Game: How to Play Impartial Combinatorial Games, by Richard K. Guy. I’ve not seen it, but it was published by COMAP; the combination of author and publisher suggests that it might be well worth looking into. (There is of course the massive Winning Ways, by Berlekamp, Conway, & Guy, ...

6

This is a most intriguing problem and took many, many, many thinking hours to solve, I even wrote a script to better understand it. It is possible for the sinners (players) to win every time. The number of players playing is irrelevant and the number of numbers they choose per turn is irrelevant as long as the players get to choose more numbers than the ...

6

For a $6 \times 3$ board, it's impossible. Consider the board below, and the squares, marked with an $\times$. $$\begin{matrix} \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \times & \cdot & \cdot & \cdot & \times & \cdot \\ \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \end{matrix}$$ The only ...

6

So, to interpret your question, you have two different procedures for filling out a table of numbers which has a definite top and left edge, but continues indefinitely down and to the right. First is Don't fill in any cell before all the positions directly above and directly to the left of it are filled. Write in each cell the smallest nonnegative ...

6

In short, because — as emphasized by the last phrase of your bolded passage — having extra pieces on the board in Tic-Tac-Toe is never bad. It's not just 'having more squares' vs. 'having fewer squares'; it's that if position A is exactly position B with an extra X on it, then position A is always at least as good for player X as position B is. ...

5

Are you including $1$ as a reasonable move? If so, this game ("Prime Nim" created by CE Shannon) has been solved. If not, the article above has Martin Gardner claiming an analysis of the strategy would be very difficult.

5

Every ordinal number $\alpha$ has a canonical copy as a surreal number $\hat\alpha$, whose left set has as members $\hat\beta$ for every $\beta\lt\alpha$, and whose right set is empty. Succinctly, $$\hat\alpha=\{\ \{\hat\beta\mathrel{:} \beta\lt\alpha\ \}\mathrel{|} \}.$$ One can prove by induction that $\alpha\mapsto\hat\alpha$ is isomorphism of the ...

5

There is unlikely to be a simple formula for general $N$ and $M$ though there will be bounds. The standard version has $N=4$ pegs drawn from $M=6$ colours, with repeats allowed. Koyama, K. and Lai, T. W. "An Optimal Mastermind Strategy." J. Recr. Math. 25, 251-256, 1993 provides an algorithm with an average of 4.340 guesses and a maximum of 6, and ...

5

You can show by induction: $N=1$ is a losing position as there is no move. $N>1$ and even is a winning position: you can subtract an odd proper divisor such as $1$ to reach an odd number $N>1$ and odd is a losing position: you must subtract an odd proper divisor to reach an even number

5

Going to higher dimension will not help; it makes the problem worse. The Hales-Jewett theorem implies that for any fixed $p$ and $n$, the first player can win the $p$-in-a-row game on the $n^d$ board for all sufficiently large $d$. So adding dimensions makes these games less fair, not more fair. For example: The first player obviously wins 2-in-a-row ...

5

Assign point $(x,y)$ the weight $2^{-(x+y)}$. Then the weight of $(x,y)$ equals the weight of $(x+1,y)$ plus the weight of $(x,y+1)$, so the total weight of the occupied points never changes. At the beginning, with a single coin at the origin, the total weight is just $1$. The points outside that square have total weight $15/16$, which is less than $1$, so ...

5

Each of the 16 pawns can move at most 6 times and there are 30 captures possible. Therefore $(16\cdot6+30)\cdot 50=6300$ is a rough upper bound (for example, not all pawns can make it to the opposite line without sometimes capturing - which would mean that sometimes pawn move and capture occur together).

4

This is a cute little problem. The insight here is to look for an invariant that is preserved by the allowed moves. In this case, the right way to approach it is to think of the original coin at the origin as having a fixed mass of 1. The rule for replacing the coin with two others can be thought of as breaking the coin in half, to be replaced by two coins ...

4

You're correct that this is a nim variant. More generally, all impartial games (those where both players have the same moves available to them) of this sort fall under the broad category of the Sprage-Grundy theorem which says that their values are equivalent to the value of some nim-pile. But for determining who's to win from a given 'single-position' ...

4

Don't think of $\ast$ as a number to begin with; that will only confuse you. $\ast$ is a mathematical object called a combinatorial game. An example of a combinatorial game you may have played before is Nim. In general, combinatorial games are characterized by having two players who take turns making moves, and also by the fact that both players have perfect ...

4

Suppose you have a subset $T$ of the set of 7 cards. Some symbols may appear an odd number of times in $T$, and some symbols an even number of times. Let $E(T)$ be the set of symbols appearing an even number of times in $T$. So $E(T)$ is a subset of your set of 6 symbols. There are $2^6=64$ different subsets of the set of 6 symbols, so 64 different ...

4

It sounds like you're asking about a variant of Nim in which the legal moves on a heap of $n$ beans are to either remove $1$ bean, or to remove no more than half the beans. As you already know, for Nim one defines the nim-sum of two heap sizes as their binary XOR; the nim-value of a position is then the nim-sum of all the heap sizes; a winning position is ...

4

Even though the infimum and supremum among numbers are equal, there are still games which are inside the gap. See Chapter 16 of ONAG (particularly, the section "Games in the Gaps"). For example, the games $+_{\alpha} = \{0|\{0|-\alpha\}\}$, where $\alpha$ is any positive surreal number, lie in the gap $1/On$. We can check this. The game $+_{\alpha}$ is ...

Only top voted, non community-wiki answers of a minimum length are eligible