Wikipedia:Reference desk/Archives/Mathematics/2015 February 6

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.

February 6

Game/puzzle with smallest game-tree complexity

Can someone please suggest a notable game or puzzle with as small a game-tree complexity as possible, say, fewer than 100 states?

The subtraction or 21 game has only 21 states but is not very well-known.

On the other hand, this table gives some examples but even tic-tac-toe has thousands.

As an illustration of SVG interactivity using SMIL, I would like to create a demonstration. Due to limitations of SMIL, each state is represented by a discrete object.

Thanks! :-) cmɢʟee⎆τaʟκ 07:44, 6 February 2015 (UTC)

Is Rock-paper-scissors of any use for you...? --CiaPan (talk) 09:37, 6 February 2015 (UTC)

Nim is slightly better known and should have a reasonable number of states. But there's a reason that well known games have large trees; a small tree would mean you could just memorize the best strategy and there would go any fun in playing it. --RDBury (talk) 11:19, 6 February 2015 (UTC)

We have an article on Nim. In the version I was taught, the starting condition was just N piles of M_n stones each (and we had to prove winning formulae for the general case). So the number of states was arbitrarily large. I see from our page that 3,5,7 heaps is one common way to play. Oh I see Nim is already linked above, 21 game is just a sub-section of Nim. SemanticMantis (talk) 15:20, 6 February 2015 (UTC)

Treating permutations as identical, there are only 48 states with initial heap sizes of 3, 4, 5, or 88 states with heap sizes of 3, 5, 7, if I counted right. -- BenRG (talk) 20:03, 6 February 2015 (UTC)

You might also try a game with a variable number of game states. The animal guessing game (not sure if it has a more formal name) is a good example. You can start with the game only having two possible answers, say "Ostrich" and "Elephant", and one question to distinguish them, like "Is it a bird ?". Once you get that working, you add more animals, like "Eagle" and "Bear", and more questions to distinguish those, like "Does it have tusks ?" and "Can this bird fly ?". This is often used as an example of an AI program, where the program builds it's own database by asking what questions can be used to distinguish the animals. However, you can also build the database manually. StuRat (talk) 16:04, 6 February 2015 (UTC)

Pong Hau K'i has 30 possible positions of pegs on a board. However they do not form a tree – if both players play safely, the game loops and never ends. --CiaPan (talk) 17:55, 6 February 2015 (UTC)

Actually in this case a game tree is infinite. --CiaPan (talk) 18:06, 6 February 2015 (UTC)

Interactive subtraction game: Players take turns removing 1, 2 or 3 objects from an initial pool of 21 objects. The player taking the last object wins.

Thank you very much, everyone, for the advice.

Rock-paper-scissors has indeed a smaller game tree, but it has randomness which is harder to implement in SMIL. As for nim, I think even if there are only 48 states (with 3/4/5), there are many more moves to arrive at that state. Good idea on the animal guessing game, though I'm unsure which article is best to illustrate it with.

I've decided to go for the subtraction game, as on the right. (I'll fix the broken thumbnail when I've the chance!)

Cheers, cmɢʟee⎆τaʟκ 09:12, 9 February 2015 (UTC)

Try micro-chess then: a board 3 rows per 2 columns, 2 pawns on each edge, ordinary steps forward and diagonal attacks, and aim of reaching the opposite side of the board. --CiaPan (talk) 10:33, 9 February 2015 (UTC)

Rearranging equation with integer division

Hi,

I am having trouble understanding how to go backwards with integer division (that is division where the remainder is ignored).

For example lets say I have function: ${\frac {337m}{11}}-2=x$

Now obviously solving for m is: ${\frac {11(x+2)}{337}}=m$

The problem is that in the first equation when m is 10, then x is 304. However in the second equation when x is 304, then m is only 9. I am having trouble understanding how to reverse the 'flooring' of the integer division. Thanks for any help.

Dacium (talk) 12:36, 6 February 2015 (UTC)

Sorry, I don't have time to type it all up, but you can work through your example using the properties described at Floor_and_ceiling_functions#Quotients. As you've demonstrated, your "solve for m" method was incorrect, because you didn't respect (or even write :) the floor function. SemanticMantis (talk) 17:13, 6 February 2015 (UTC)

Keep in mind that, for any fixed non-zero divisor, integer division (as a function of one variable) is many-to-one. In the explanation that follows, integer division is rewritten explicitly as taking the floor of a real division. In your example, $\left\lfloor {\frac {337m}{11}}\right\rfloor =x+2$ means that $11(x+2)\leq 337m<12(x+2)$. You cannot infer that $337m$ equals to any particular value. It would be wrong to infer that $337m=11(x+2)$. --173.49.18.95 (talk) 04:34, 7 February 2015 (UTC)