Infinite queens on an infinite chessboard

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Infinite queens on an infinite chessboard

Postby skeptical scientist » Wed Jun 24, 2009 6:49 am UTC

Can you place infinitely many queens on an infinite chessboard so that every row, column, and diagonal contains exactly one queen?

(Inspired by the other queen thread, obviously.)
Spoiler:
This one should be pretty easy; there exists a one-line solution.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Walter.Horvath
Posts: 933
Joined: Fri May 15, 2009 11:33 pm UTC
Location: Orlando, FL

Re: Infinite queens on an infinite chessboard

Postby Walter.Horvath » Wed Jun 24, 2009 6:55 am UTC

If I had to guess,

Spoiler:
I'd say yes.

Expanding sets that were previously complete in 8x8 to one more row/column on each edge seems to suggest that there will always be some more room? Wait, let me expand it out some more...

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Infinite queens on an infinite chessboard

Postby aleph_one » Wed Jun 24, 2009 7:21 am UTC

Yes. Here's a cheap, non-constructive argument.

Spoiler:
Since there are countably many rows, columns, and diagonals we wish to satisfy (call these regions), we may list them. We construct the arrangement by the following infinite process:

In step i, we will satisfy region i of the list. If this region already has a queen, we're done. If not, place a queen in the region that does not attack any already-placed queens. This is possible, since any queen not in the region attacks finitely many squares in the region, and only finitely many queens have been placed, so only a finite number of squares are excluded.

This solution generalizes to placing non-attacking pieces so that each region has a prescribed number of pieces as long as:
    - There are countably many regions.
    - Each region is infinite.
    - Each piece not in a region attacks finitely many squares in that region.

I'd like to see a nice, constructive solution for this, and for the more strict problem in which each arithmetic progress of squares (meaning that the vector offset is constant) has exactly one queen.

Edit:
Spoiler:
A "greedy" solution for the quarter plane places queens on the zero-value spaces of Wythoff's Nim game. See here http://home.att.net/~numericana/answer/games.htm#wythoff.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Infinite queens on an infinite chessboard

Postby quintopia » Wed Jun 24, 2009 7:28 am UTC

Re:constructive solution w/ arithmetic progressions: I can't put it algebraically, but it looks impossible. It seems like the distance to adjacent queens must grow exponentially in some measure.

Basically, I can find no nice neat set of arithmetic progressions that you can just sort of tile with.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Wed Jun 24, 2009 7:30 am UTC

Not quite a one-liner:
Spoiler:
Number all the columns, using some bijection from N to Z. For example, 0->0, 1->1, 2->-1, 3->2, 4->-2, ..., 2n->-n, 2n+1->n.
Do the same for the rows, and for the two sets of diagonals.
Place the queens one by one using the following procedcure:
1a. Find the row with the lowest index number that doesn't yet contain a queen.
1b. Put the next queen in that row on any any unattacked square.
2a. Find the column with the lowest index number that doesn't yet contain a queen.
2b. Put the next queen in that column on any any unattacked square.
3a. Find the \ diagonal with the lowest index number that doesn't yet contain a queen.
3b. Put the next queen in that \ diagonal on any any unattacked square.
4a. Find the / diagonal with the lowest index number that doesn't yet contain a queen.
4b. Put the next queen in that / diagonal on any any unattacked square.
5. Repeat ad infinitum.

Clearly the row/column/diagonal with index number n will be covered after 4n queens have been placed. Therefore all rows/columns/diagonals will be covered.

If that one-liner hint was intended as a clue to using queens on a single knights-move line (n,2n), then you were mistaken. That doesn't cover all diagonals, e.g. the diagonal (1+k,1-k).


Edit: Ninja'd - I'm too slow.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Infinite queens on an infinite chessboard

Postby Token » Wed Jun 24, 2009 9:51 am UTC

jaap wrote:
Spoiler:
If that one-liner hint was intended as a clue to using queens on a single knights-move line (n,2n), then you were mistaken. That doesn't cover all diagonals, e.g. the diagonal (1+k,1-k).

Spoiler:
It wouldn't even cover all rows. It's clear there's no one-line solution in the sense that all the queens lie on a single line - the only way of covering all rows and columns with a single line is to have all the queens on the same diagonal.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite queens on an infinite chessboard

Postby skeptical scientist » Wed Jun 24, 2009 10:47 am UTC

The "one-line" solution I had in mind was indeed aleph_one's. I guess it's not quite one-line, but
Spoiler:
Fix a bijection between N and the set of rows, columns, and diagonals. Place the nth queen somewhere in the first row/column/diagonal that doesn't contain any of the first n-1 queens, somewhere which isn't attacked by any of the first n-1 queens.
is pretty close. I of course meant that the proof was one-line, not that the queens were all on a single line.

This solution is not constructive as given, but it's not hard to turn it into a constructive proof - just make all your choices constructively. (I think constructive proofs are only preferable to non-constructive ones when they provide further insight, which is clearly not the case here.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Infinite queens on an infinite chessboard

Postby Nitrodon » Thu Jun 25, 2009 7:01 am UTC

A constructive method:
Spoiler:
Step 1:

Code: Select all

.X...
....X
..X..
X....
...X.

Step 2:

Code: Select all

.A...
....A
..A..
A....
...A.

where A is the 5x5 block from step 1.
etc.

The middle ceil(5n/2) diagonals will all be covered exactly once on step n.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite queens on an infinite chessboard

Postby skeptical scientist » Thu Jun 25, 2009 8:29 am UTC

Nitrodon, it looks like your method is missing some diagonals.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Sir Fluffum
Posts: 11
Joined: Thu Jun 25, 2009 10:37 am UTC

Re: Infinite queens on an infinite chessboard

Postby Sir Fluffum » Thu Jun 25, 2009 10:51 am UTC

I might have missed some diagonals. I didn't bother to check.
You can if you want to.

Spoiler:

Code: Select all

.x.......
...x.....
x....x...
..x....x.
....x....
......x..
........x


continue infinitely


Edit:I just noticed that all the rows contain two.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Infinite queens on an infinite chessboard

Postby aleph_one » Thu Jun 25, 2009 9:07 pm UTC

I also thought that Nitrodon's construction missed diagonals, but on investigating further, it seems it hits all of them. It appears that the missed diagonals of each cell level are taken care of by another cell of the same level.

Is there an easy way to show that it hits all the diagonals?

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Infinite queens on an infinite chessboard

Postby dedalus » Fri Jun 26, 2009 8:27 am UTC

I think the proof would be in the fact that for any individual square there are two straight (horizontal + vertical) and two diagonals; ergo on an infinite board there are as many diagonals as there are straight lines. Thus, if the proof works for straight lines it will also work for the diagonals. It falls apart on a non-infinite board because there are more diagonal lines then there are straight lines, but you can't do this for a non-infinite board anyway (if it's not square then you need more queens to fulfill the vertical lines then the horizontal or the other way around, if it is square all corners must be filled to fill up the diagonals that only cross the corner of that square, but then the two diagonals of the square remain unfulfilled).

Edit: sorry, as there are as many straight lines as there are diagonal lines, as long as the horizontal/vertical conditions have been fulfilled AND there is max 1 queen per diagonal there must be one queen for every diagonal.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Fri Jun 26, 2009 1:32 pm UTC

dedalus wrote:Edit: sorry, as there are as many straight lines as there are diagonal lines, as long as the horizontal/vertical conditions have been fulfilled AND there is max 1 queen per diagonal there must be one queen for every diagonal.


That argument (the pigeonhole principle) doesn't work when you have infinitely many items.
For example, there are just as many normal numbers as there are even numbers. That doesn't mean there are no gaps in there which form the odd numbers.
Just because every column/row is covered, doesn't mean there are no gaps in the coverage of the diagonals.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Infinite queens on an infinite chessboard

Postby Nitrodon » Sat Jun 27, 2009 12:51 am UTC

I recently figured out a good proof for my solution.
Spoiler:
Theorem:
The solution I posted earlier works, where the limit is taken with the center fixed.

Proof:
We must use two important facts about the 5x5 cell (easily verified by observation):

1) It is a solution to the 5-queen problem on a 5x5 torus.
2) There are queens covering both center diagonals and the diagonals adjacent to them.

Inductively, we will first prove that the board is a solution to the 5n-queen problem on a 5nx5n torus for each iteration. By (1), this holds for the original 5x5 cell (i.e., the base case). Suppose it holds for the (n-1)th iteration, and consider the nth iteration (in which each queen in the 5x5 cell is replaced by the current board. Each row/column/diagonal of the 5nx5n torus includes either 1 or 2 row/column/diagonals of the 5x5 torus, and each of those will hit exactly one of the 5n-1x5n-1 boards. In fact, the intersection will correspond precisely with a row/column/diagonal on the 5n-1x5n-1 torus. Thus, there is exactly one queen in that row/column/diagonal, and the new board is a solution to the 5n-queen problem on a 5nx5n torus.

To show that each diagonal is covered, we must use (2). In any iteration, each row, column, and diagonal through the center 5n-1x5n-1 board goes through the center row/column/diagonal of the 5x5 and possibly one of the two adjacent diagonals. As a result, it intersects the entirety of the corresponding row/column/diagonal of the 5n-1x5n-1 torus, and thus contains exactly one queen. Each row/column/diagonal of the infinite board will eventually go through the 5nx5n board at some iteration, and thus will go through the center board of all later iterations. Thus, every row, column, and diagonal is covered exactly once. QED

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite queens on an infinite chessboard

Postby skeptical scientist » Sat Jun 27, 2009 2:09 am UTC

Ah, that's clever.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Infinite queens on an infinite chessboard

Postby dedalus » Sat Jun 27, 2009 11:38 am UTC

jaap wrote:That argument (the pigeonhole principle) doesn't work when you have infinitely many items.
For example, there are just as many normal numbers as there are even numbers. That doesn't mean there are no gaps in there which form the odd numbers.
Just because every column/row is covered, doesn't mean there are no gaps in the coverage of the diagonals.

But that argument fails because of the differing sizes of infinity (i think), and if n is the number of even numbers between 1 and x, the total number of natural numbers = 2n, and this continues to occur as x->infinity. The point is that on any finite board size there are more diagonals then columns/rows because there is a left down diagonal from every square along the top and every diagonal down the side (as opposed to e.g. there is a column only for every square along the top). But, on an infinite board there are no sides, and thus we can reduce the number of diagonals to the number of columns/rows, and I can't see any much logical fallacy in that. If you define the infinite board to have a definite edge, even at infinity, then the top left corner and bottom right corner must be filled, and they would be on the same diagonal.

However, seeing as Nitrodon has made a much more formal and better proof then this, it's fairly redundant.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

dasada122
Posts: 88
Joined: Sun Jun 14, 2009 8:41 pm UTC
Location: Wherever you aren't looking at the moment.

Re: Infinite queens on an infinite chessboard

Postby dasada122 » Sun Jun 28, 2009 1:55 am UTC

I'm not a mathmind just yet, but if there are infinite Queens and infinite spaces, doesn't each space have a queen?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Infinite queens on an infinite chessboard

Postby quintopia » Sun Jun 28, 2009 2:05 am UTC

dasada: no. This is what was just mentioned above, and you can see several threads about it in the math forum. To put it concisely, if you have an infinite set A and and infinite set B you can have A=B or A is a subset of B or B is a subset of A or none of the above. Infinitude doesn't give you any nice properties without more information.

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Re: Infinite queens on an infinite chessboard

Postby userxp » Mon Jul 20, 2009 6:57 pm UTC

1. Put a queen on arbitrary square
2. Find closest unattacked square (if there are more than one, choose anyone)
3. Place queen on that square
4. GOTO 2

Wouldn't that work?

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Mon Jul 20, 2009 7:29 pm UTC

userxp wrote:1. Put a queen on arbitrary square
2. Find closest unattacked square (if there are more than one, choose anyone)
3. Place queen on that square
4. GOTO 2
Wouldn't that work?


Maybe, maybe not. You'll have to prove it.
While it is certainly true this method will ensure every square eventually gets attacked (or gets a queen), who's to say there isn't some row/column/diagonal that never gets a queen? Each time you place a queen an infinite number of squares get attacked that weren't being attacked before. Maybe those happen to keep covering up one row/column/diagonal fast enough that it never contains the nearest unattacked square.

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Re: Infinite queens on an infinite chessboard

Postby userxp » Mon Jul 20, 2009 11:09 pm UTC

I feel stupid. Only now I have noticed that this is not equal to the n-queens problem for n=∞ (i.e. that you must not only place infinite queens without attacking, you have to place one on each row/column/diagonal).
I have even made a crappy OO.Calc macro to try it:
Spoiler:
Image
"Q" is the initial queen, "X" are the others. Green cells are attacked by some queen.

Anyway I think this time I got the real solution:
Spoiler:
Yes, you can: If you pick any row/column/diagonal that does not have a queen and go far enough, you will always find a free spot.

Explanation:
You can put a queen on every square that is not attacked. For a column to be impossible to have a queen, there should be other queens attacking it, but since the board is infinite, there will always be one more square. Same for rows and diagonals.
Process:
For each square, if the square is attacked by < 3 queens, there must be at least one unattacked square in the same row/column/diagonal. Put a queen there and repeat.
Once this is done each square will be attacked vertically, horizontally and diagonally, which means that there is one queen in every row/column/diagonal.

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Infinite queens on an infinite chessboard

Postby dedalus » Tue Jul 21, 2009 2:12 am UTC

I'm pretty sure that the proof fails because of the boundaries of infinitude. It's a similar thing to saying 'for every number between 0 and 1, I can double it to get a number between 0 and 2, thus as all those numbers between 0 and 1 are also included in the set between 0 and 2, there are no numbers in between 1 and two. Basically, as you continue to push out to find squares that aren't attacked and put queens in them, you have no way of proving that the boundaries you're setting on the currently-filled space aren't expanding faster then the number of squares that are being attacked by 4 queens.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: Infinite queens on an infinite chessboard

Postby gcoope » Tue Jul 21, 2009 7:48 am UTC

That's not quite right userxp, you can't guarantee that you will ever get to a specified row/column/diagonal.

However with a little twerk:

Spoiler:
There are a countably finite total number of rows/columns/diagonals. Therefore we can give them an index with the natural numbers.

For the lowest index line which isn't covered place a queen in an arbitrary uncovered spot on the line.

Repeat.


Now certainly every line will get covered, and there will always be an available spot (only finitely many can be covered out of an infinite number of options).

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Tue Jul 21, 2009 8:29 am UTC

userxp wrote:Anyway I think this time I got the real solution:
Spoiler:
Yes, you can: If you pick any row/column/diagonal that does not have a queen and go far enough, you will always find a free spot.

Explanation:
You can put a queen on every square that is not attacked. For a column to be impossible to have a queen, there should be other queens attacking it, but since the board is infinite, there will always be one more square. Same for rows and diagonals.
Process:
For each square, if the square is attacked by < 3 queens, there must be at least one unattacked square in the same row/column/diagonal. Put a queen there and repeat.
Once this is done each square will be attacked vertically, horizontally and diagonally, which means that there is one queen in every row/column/diagonal.


That's very nice, and it works. So the procedure is now:
Spoiler:
1. Find the empty square nearest the origin that isn't being attacked by 4 queens.
(not 3 - remember there are 2 diagonals)
2. Find a row/column/diagonal containing that square but not containing a queen.
3. Find an unattacked square in that row/column/diagonal and place a queen there.
4. Goto 1.

Clearly every square will eventually contain a queen or be attacked by four queens, because there are only a finite number of squares closer to the origin. Also, the procedure will never place two queens in the same row/column/diagonal. Therefore every empty square will eventually have its row/column/diagonals each contain exactly one queen. Therefore every row/column/diagonal will eventually contain exactly one queen.

By using the nearest square you implicitly set up this indexing/ordering of the rows/columns/diagonals that's been mentioned.

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Infinite queens on an infinite chessboard

Postby dedalus » Tue Jul 21, 2009 10:09 am UTC

Jaap, I might be wrong, but as the area containing queens would expand at a rate greater then the area with the conditions fulfilled, wouldn't you by definition never be able to finish this?

For clarification, If we have a finite square, then there are always 2x-1 left or right diagonals where x is the number of columns or rows. However, seeing as any square lies on just 1 left diagonal, 1 right diagonal, 1 column and 1 row, can we say that an infinite board has the same number of rows and columns as it does diagonals?
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Tue Jul 21, 2009 12:11 pm UTC

dedalus wrote:Jaap, I might be wrong, but as the area containing queens would expand at a rate greater then the area with the conditions fulfilled, wouldn't you by definition never be able to finish this?


Well, how do you finish an infinite task? I think that is an unanswerable question really.
However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

dedalus wrote:For clarification, If we have a finite square, then there are always 2x-1 left or right diagonals where x is the number of columns or rows. However, seeing as any square lies on just 1 left diagonal, 1 right diagonal, 1 column and 1 row, can we say that an infinite board has the same number of rows and columns as it does diagonals?


The number of rows is the same as the number of columns, is the same as the number of diagonals, and is the same as the number of squares. Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Infinite queens on an infinite chessboard

Postby dedalus » Tue Jul 21, 2009 12:14 pm UTC

jaap wrote:Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...
jaap wrote:However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite queens on an infinite chessboard

Postby jaap » Tue Jul 21, 2009 12:22 pm UTC

dedalus wrote:
jaap wrote:Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...


I was not being sarcastic. They are all the same number (or cardinality to be precise). They are all Countably infinite.

dedalus wrote:
jaap wrote:However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.


They all lie within the infinite chessboard.
There is no finite rectangular chessboard on which you can place a single queen in every row/column/diagonal, other than the trivial 1x1 case.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Infinite queens on an infinite chessboard

Postby douglasm » Tue Jul 21, 2009 1:15 pm UTC

dedalus wrote:
jaap wrote:Just as the number of natural numbers is the same as the number of even numbers, the number of odd numbers, and the number of rationals.

Ummm... it's definitely not the same number. So yeah...

Counting and equivalencies and such get a bit weird when infinite quantities are involved. Regardless of what your intuition might say about it, all four sets of numbers he mentioned are in fact the same size. If you can transform one set into another by using only 1-to-1 replacements, the two sets have the same size. You can transform the natural numbers into the even numbers by simply replacing every number with its double. You can transform the natural numbers into the odd numbers by replacing every number with its double minus 1. The rationals are a bit trickier, but one way is to put them in order by the sum of the numerator and denominator (ties resolved by the numerator) and then just count how far down the list each number is. 1 gets replaced by 1, 2 by 1/2, 3 by 2, 4 by 1/3, 5 by 3, 6 by 1/4, 7 by 2/3, 8 by 3/2, 9 by 4, and so on. Every natural number gets replaced with a different rational number, and no rational numbers are omitted - for any given rational number it is possible to find its position in the list in finite time - , so the end result is a size-preserving transformation between the set of natural numbers and the set of rational numbers.

dedalus wrote:
jaap wrote:However, you can show any particular finite region of the infinite chessboard, however large that given region is, will have all its rows/columns/diagonals covered by a queen before some finite number of queens have been placed. You can even give a upper bound on how far the queens need to be.

But, you can't prove that all those queens will lie within that region. I don't think that's the intent of the OP.

You don't need to. Row 10 could be covered by a queen fifty trillion spaces away and it would still count.

hnooch
Posts: 128
Joined: Mon Nov 26, 2007 6:55 pm UTC

Re: Infinite queens on an infinite chessboard

Postby hnooch » Tue Jul 21, 2009 10:24 pm UTC

gcoope wrote:That's not quite right userxp, you can't guarantee that you will ever get to a specified row/column/diagonal.

However with a little twerk:

Spoiler:
There are a countably finite total number of rows/columns/diagonals. Therefore we can give them an index with the natural numbers.

For the lowest index line which isn't covered place a queen in an arbitrary uncovered spot on the line.

Repeat.


Now certainly every line will get covered, and there will always be an available spot (only finitely many can be covered out of an infinite number of options).

Nice! I wonder if there's a "nice" indexing which makes the pattern particularly easy to describe? Somehow I doubt that there's a nice way to find an index but there might still be a nice way to describe where the queens actually get placed.

adamadam
Posts: 3
Joined: Thu Jul 23, 2009 9:47 am UTC

Re: Infinite queens on an infinite chessboard

Postby adamadam » Thu Jul 23, 2009 10:09 am UTC

I came to the same solution as nitrodon did before reading the topic, it's defiantly the correct one,
Spoiler:
and you don't need numbers to prove it, just squared paper.
It's simply a fractal where the edges and center of the swastika is the repeating pattern. It's simple, easy to check and would allow you to place the queens at a much higher rate than the four step trial and error method. Not that the speed is relevant in an infinite environment, but I think it's enough to determine that it's a more effective solution.

I really suck at formulating math and it's been a while since I did it, so this is the best formula I could produce, it's probably incorrect in it's formulation, I'd like it if someone much better at math syntax understands my formula and corrects it.
Queens at : X(0,0) and {[X(+2,+1), X(+1,+2), X(-2,-1), X(+1,-2)] * 5} ^ i

L337R3dN3k
Posts: 65
Joined: Sun Jul 26, 2009 6:37 am UTC

Re: Infinite queens on an infinite chessboard

Postby L337R3dN3k » Mon Jul 27, 2009 7:16 am UTC

Here's a little insight into the problem:
Spoiler:
We seem to be assuming through this entire discussion that the size of the chessboard is countably infinite. This needs to be made explicit, as the case in which the chessboard is uncountable but the number of queens countable is not possible.

Assume the size of the chessboard is uncountably infinite, presumably (but not necessarily) implying the numbers of rows, columns, and diagonals are all uncountably infinite, and assume the number of queens is countably infinite.

Since the number of queens is countable, we will lazily number them with the integers.
Since the chess board is uncountable, we can think of it as the set of all real numbers -- any reasonable attempt to cover it with queens will result in an infinite number of spaces lying between each pair of queens. Since we are attempting to cover three different directions in this manner, the queens must be staggered -- meaning there are infinite numbers of spaces in at least two directions between each pair of regularly spaced queens. Since the queens can only provide linear coverage, this implies most of the intervening spaces must be uncovered.


Spoiler:
Assuming the size of the chessboard is countable, I believe jaap's approach will work nicely. Unfortunately, if both the size of the chessboard and the number of queens are uncountable the numbering system breaks down. We could probably find a way to cover the chessboard with the set of real numbers (though it might be easier with the set of complex numbers?), but then we would need to find a way to traverse the entire set.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Infinite queens on an infinite chessboard

Postby aleph_one » Mon Jul 27, 2009 7:36 am UTC

If the chessboard is [imath]\mathbb{R}\times\mathbb{R}[/imath] rather than [imath]\mathbb{Z}\times\mathbb{Z}[/imath], we can do a similar non-constructive argument if we well-order the lines on the chessboard. This will require the axiom of choice, which is equivalent to the well-ordering principle, and the continuum hypothesis, to guarantee to each queen is preceded by only countably many queens, so a non-attacked spot along the desired line remains.

(Actually, is the continuum hypothesis needed? I think the argument still works if the number of predecessors to each queen in the ordering is a cardinality intermediate to that of [imath]\mathbb{Z}[/imath] and [imath]\mathbb{R}[/imath]. Can it be shown that a subset of [imath]\mathbb{R}[/imath] with such a cardinality has measure 0?)

Of course, if we assume the queen's attack lines are still the standard vertical, horizontal, and diagonal lines, there is a simple constructive solution of placing the queens along any straight line other a horizontal, vertical, or diagonal.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite queens on an infinite chessboard

Postby skeptical scientist » Mon Jul 27, 2009 8:37 am UTC

aleph_one wrote:I think the argument still works if the number of predecessors to each queen in the ordering is a cardinality intermediate to that of [imath]\mathbb{Z}[/imath] and [imath]\mathbb{R}[/imath]. Can it be shown that a subset of [imath]\mathbb{R}[/imath] with such a cardinality has measure 0?
Yes.

Lemma: Let X be a positive measure subset of R. Then there is a closed subset Y of X with positive measure.

Proof: Let I be a closed interval such that [imath]X \cap I[/imath] has positive measure. Then [imath]\lambda(X \cap I)=\lambda(I)-\lambda(I \setminus X)>0[/imath], so [imath]\lambda(I \setminus X)<\lambda(I)[/imath]. By definition, [imath]\lambda(I \setminus X)=\inf\{\lambda(U) : U \supset I \setminus X \text{ is open}\}[/imath], so there is an open set U containing I \ X with [imath]\lambda(U)<\lambda(I)[/imath]. Then [imath]I \setminus U[/imath] is a closed subset of X with positive measure.

Theorem: Let X be a positive measure subset of R. Then X has cardinality c, the cardinality of the continuum.

Proof:
By the lemma, we may assume X is closed. Since X has positive measure, there are disjoint closed intervals I0 and I1 of finite length such that each intersects X in a set of positive measure. Given Is which intersects X in a set of positive measure, iteratively construct disjoint closed subintervals Is0 and Is1 such that each intersects X in a set of positive measure. In this way, we iteratively construct intervals It for all finite strings [imath]t[/imath] of 0s and 1s, such that if [imath]s[/imath] is a substring of [imath]t[/imath], then [imath]I_t \subset I_s[/imath], and if s and t are different strings of the same length, Is and It are disjoint.

For each s, let xs be an element of [imath]I_s \cap X[/imath]. Given a sequence f of 0s and 1s, let xf be a limit point of {xs : s is an initial segment of f}. Since this set is bounded (it is a subset of I0 or I1) it contains a limit point. Since X is closed, this point is an element of X. Let f and g be distinct sequences of 0s and 1s. Then they differ at some position n; let u and v be the n-place initial segments of f and g, respectively. Then all but n-1 elements of {xs : s is an initial segment of f} are elements of Iu, so [imath]x_f \in I_u[/imath]. Similarly, [imath]x_g \in I_v[/imath]. Since Iu and Iv are disjoint, xf and xg are distinct. Thus {xf : f is an infinite sequence of 0s and 1s} is a subset of X of cardinality c.



However, you don't need to use measure. Each point you put a queen takes out at most three points on any line that doesn't contain that queen, so a simple cardinality argument suffices. Just be sure that your well-order has minimal type, so that no element has c-many predecessors.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Infinite queens on an infinite chessboard

Postby aleph_one » Mon Jul 27, 2009 8:41 pm UTC

skeptical scientist wrote: ...so a simple cardinality argument suffices...


Doh! I don't know why was so set on using measure when I only needed the difference of two sets to be non-empty.

Thanks, skeptical scientist, for the nifty proof of the measure result. I like how closure was used to show that the set contains an uncountably real number of distinct limit points.

wpaulsen
Posts: 1
Joined: Wed Oct 25, 2017 4:40 pm UTC

Re: Infinite queens on an infinite chessboard

Postby wpaulsen » Wed Oct 25, 2017 5:26 pm UTC

We can place the queens using a recursively defined function f(x), which is one-to-one and onto on the set of all integers, such that f(-x) = -f(x) = f^(-1)(x), and g(x) = f(x)-x is also one-to-one and onto. Then place the queens at the coordinates (x, f(x)) for all integers x. The fact that g(x)
is one-to-one and onto proves that every diagonal contains exactly one queen in one direction, and the symmetry gives us the result in the other direction.

Spoiler:
Start with f(0) = 0, so that g(0) = 0. For i = 1, 2, ..., if f(x) = i for some value previously defined, then f(i) = -x, and g(i) = -x-i. Otherwise, we let k be the largest value of g(x) defined so far, and add 1. If g(x) = -k for some previously defined x, then we add one again. Then g(i) = k, and f(i) = i+k. Finally, we place the queens at the coordinates (x, f(x)) for all integers x.

The sequence of f(x) and g(x) for non-negative x is:
f(x) = {0, 2, -1, 5, 8, -3, 11, 13, -4, 16, 19, -6, 22, -7, 25, 28, -9, 31, 33, -10, 36, 39, -12, 42, 45, -14, 48, 50, -15, 53, 56, -17, 59, ...}
g(x) = {0, 1, -3, 2, 4, -8, 5, 6, -12, 7, 9, -17, 10, -20, 11, 13, -25, 14, 15, -29, 16, 18, -34, 19, 21, -39, 22, 23, -43, 24, 26, -48, 27, ...}

Here is a portion near the center of the board:

Code: Select all

....................o......
...........................
...................o.......
...........................
...........................
.................o.........
o..........................
..o........................
................o..........
.....o.....................
........o..................
..............o............
...........o...............
.............o.............
...............o...........
............o..............
..................o........
.....................o.....
..........o................
........................o..
..........................o
.........o.................
...........................
...........................
.......o...................
...........................
......o....................

This might be considered as a "two line solution" but the lines are at an irrational slope. The main line has a slope of about 1.839. It would be curious to determine the eventual slope of the line.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests