Clever.
How many distinct chess games are possible, and which is the longest?
Sort:
Aarrgh yup double counted the queen controlling its antipode.
Ah, clever. The symmetry of the toroidal board under translation allows us to show there is only that one possible pattern of queens on 1 colour complex.
Neat.
Someone should make a chess puzzle book with questions like these. Or I guess you'd call it a chess themed logical puzzle book or something.
yeah, at first I thought I was going to have to go through six cases on the second move(I saw the reflection across the a1-h8 diagonal immediately) and then I saw there were really only two cases which made things much nicer. Then everything ended up falling into that pattern which was ever so nice.
I've been thinking a little about how many possible combinations with six queens are there(I've been doing an unlabelled board) I've got that there are 16(2x2x4)distinct combinations using 4 queens on one color. My original example shows that 6 can be done with 3 on each color, but I haven't found a good way to count the number of ways to put 3 on each color.
"I would like to see the proof of that upper bound of 10^46 for legal positions. I'm curious to see how they counted."
See also: http://homepages.cwi.nl/~tromp/chess/chess.html
counting total chess positions (achievable + non-achievable) is possible and you get the exact number, because you can formulate a mathmetical formula and use a programming language.
but you probably cannot do that for counting the longest possible chess game. hence you cannot get the exact number. (to compare two lines they are stored in RAM, but in this case the lines are too large that very quickly it goes outsite any RAM's capacity.)
About the 8 queens problem on a torus:
A very simple, alternate proof that 8 non-attacking queens is impossible can be obtained by inspecting the 12 basic solutions to the regular 8 queens problem. Clearly the torus solutions would also be regular solutions, but in each of the basic solutions the change in topology causes some queens to attack each other. Removing a necessary amount of the misbehaving queens gives a nice amount of 6 queen solutions for the toral board.
This could then be generalized for the n queens problem, since there is a simple (but tedious) determinant method for solving the regular n queens problem. Of course this is a very brutal way, but works for checking some fixed n.
Uncia,
That is a way of checking that 8 queens is impossible on an 8x8 tarus board, and I could see how this would also show if n queens is possible on an nxn board.
But, I don't think that method shows that seven isn't possible, as there is no reason to assume that the only plausable patterns with seven queens are present in the 12 "pure" solutions. If you had an exhaustive list(complete with proof of exhaustion) of all ways to put seven queens on a chess board, then checked their legality on the toroidal board that would suffice, but I don't know if that kind of groundwork has been laid out yet(at least in general, I believe boards of 3nx3n have been studied extensively though)
So while your method definitely can use pre-existing work to save some time with regards to the problem "n queens on an nxn toroidal board", if n queens do not work, the maximum number stays elusive.
True, I only posted that as a simple proof for the impossibility of 8 queens on an 8x8 board. Your proof is superior in that it determines the maximum number of non-attacking queens on an 8x8 toroidal board. The comment on the 6 queens was just a way of obtaining a large number (due to the symmetries present) of 6-queen solutions for this case.
The determinant method, I noticed, can readily be modified to the nxn toral case so that there is no need to go through the regular solutions. This gives a purely algebraic method of checking the general case n. The answer is already known, but it was nice to notice the pattern for e.g. n=2k. Again this also leaves the question about the maximum number of queens open, but it answers the basic problem effectively.
Here's another related question I've been thinking about. Asking the same questions about bishops on a toroidal board. You can quickly see that 8 is the maximum(there are only 8 / diagonals and 8 \ diagonals, so you definitely couldn't have 9):
So, that wasn't particularly hard. Trying to count the number of solutions with 8 bishops though...So far, I've attempted to find a way to "transform" the current solution into other solutions, in hopes to maybe find a way to count using this idea. So far, it appears there are two "basic" transformations, either you can take a single bishop to its anti-podal point: or you can move two bishops of the same color to the two points of intersection between their diagonals: With these two transformations, you can acomplish all basic translations, which leads me to believe that these transformations describe all the possible arrangements. How to count without counting duplicates or how to prove that all arrangements of 8 independant bishops on a toroidal board can be achieved from the intial position(8 in a straight line) using only these two transformations escapes me. Any ideas?
So, it ends up that the first basic transformation can be thought of as a special case of the second basic trasnformation(specifically when you choose the same bishop twice), so the total number of basic transformations is twice the number of times you can choose 2 from 4 with repetition, so there are only 20 possible basic transformations.
Math Puzzle:
Seven men engaged in play. Whenever a player won a game he doubled
the money of each of the other players. That is, he gave each player just as much money as each had in his pocket. They played seven games and,
strange to say, each won a game in turn in the order of their names, which began with the letters A, B, C, D, E, F, and G.
When they had finished it was found that each man had exactly $1.28 in his pocket. How much had each man in his pocket before play?
Here is my puzzle:
Three boys, Adam, Bob and Chris play a game in rounds, In each round one of them sits out, the other two toss a fair coin. The one losing the coin toss sits out in the next round and the winner plays with the one sitting out in the previous round. The boy winning two tosses in a row wins the game. In the first round Adam sits out.
What are the probabilities of each boy winning the game?
@205
after 2 rounds, there is 25% chance A wins, 25% chance B wins.
50% chance Game continues.
Theoretically it can be a infinite number of Rounds.
The number of rounds can be 'infinite', but the probabilities are finite and can be given in a closed form. They are rational numbers.
What are those probabilities?
Dec 25, 2014
0
#197
On a related note, is there any way to find what would be the minimum no. of moves required to arrive at a stalemate (with help from both sides)?
It is believed to be 10 moves but till now no proof if available (at least I am not aware of) that < 10 is not possible. Any thoughts from others please..
Cheers,
Arun
kiloNewton's ABCDEFG puzzle: Respectively at the start, ABCDEFG had $4.49, $2.25, $1.13, $0.57, $0.29, $0.15, $0.08.
watcha's puzzle: A has a 2/7 chance of winning, B and C each 5/14.
[edit]
For watcha's puzzle:
The game isn't guaranteed to continue so it seems Adam has the worst chance, and Bob and Chris have equal chances.
Remellion wrote:
kiloNewton's ABCDEFG puzzle: Respectively at the start, ABCDEFG had $4.49, $2.25, $1.13, $0.57, $0.29, $0.15, $0.08.
watcha's puzzle: A has a 2/7 chance of winning, B and C each 5/14.
Oops, I read who has the best chance, not what are the probabilities.
I get these numbers too.
For example I got A with summation of 1/ 2^(3+3n) = 1/7 then added to itself = 2/7
B and C got 2+3n added to 4+3n
3n because after losing a flip, they need the next 3 coin flips to go their way to win.
As for kilonewton's problem I don't understand your solution. Each person will have their money doubled 6 times, so it seems they should all start with the same amount. (Oh I see, they're paying out of their own pocket each time)
ohh, and this extends quickly to show that 7 cannot happen either. for 7 to happen, at least 4 must be on one color, so this shape occurs:
Here, the white pieces represent the remaning squares where queens could be put. Now, observe that placing a queen on any of white's bishops would eliminate the posibility that you could put another on a bishop. Similarly, putting a queen on one of the knights eliminates the posibility of putting another one on a knight. Since this is all the possible squares, a maximum of two other queens may be placed on the board. Thus seven is not possible.