(Inspired by the other queen thread, obviously.)
Infinite queens on an infinite chessboard
Moderators: jestingrabbit, Moderators General, Prelates
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Infinite queens on an infinite chessboard
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.)
(Inspired by the other queen thread, obviously.)
Spoiler:
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
"With math, all things are possible." —Rebecca Watson

 Posts: 933
 Joined: Fri May 15, 2009 11:33 pm UTC
 Location: Orlando, FL
Re: Infinite queens on an infinite chessboard
If I had to guess,
Spoiler:
Re: Infinite queens on an infinite chessboard
Yes. Here's a cheap, nonconstructive argument.
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:
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:
Re: Infinite queens on an infinite chessboard
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.
Basically, I can find no nice neat set of arithmetic progressions that you can just sort of tile with.
Re: Infinite queens on an infinite chessboard
Not quite a oneliner:
Edit: Ninja'd  I'm too slow.
Spoiler:
Edit: Ninja'd  I'm too slow.
Re: Infinite queens on an infinite chessboard
jaap wrote:Spoiler:
Spoiler:
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Infinite queens on an infinite chessboard
The "oneline" solution I had in mind was indeed aleph_one's. I guess it's not quite oneline, butis pretty close. I of course meant that the proof was oneline, 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 nonconstructive ones when they provide further insight, which is clearly not the case here.)
Spoiler:
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 nonconstructive 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
"With math, all things are possible." —Rebecca Watson
Re: Infinite queens on an infinite chessboard
A constructive method:
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Infinite queens on an infinite chessboard
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
"With math, all things are possible." —Rebecca Watson

 Posts: 11
 Joined: Thu Jun 25, 2009 10:37 am UTC
Re: Infinite queens on an infinite chessboard
I might have missed some diagonals. I didn't bother to check.
You can if you want to.
Edit:I just noticed that all the rows contain two.
You can if you want to.
Spoiler:
Edit:I just noticed that all the rows contain two.
Re: Infinite queens on an infinite chessboard
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?
Is there an easy way to show that it hits all the diagonals?
Re: Infinite queens on an infinite chessboard
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 noninfinite board because there are more diagonal lines then there are straight lines, but you can't do this for a noninfinite 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.
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.
Re: Infinite queens on an infinite chessboard
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.
Re: Infinite queens on an infinite chessboard
I recently figured out a good proof for my solution.
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Infinite queens on an infinite chessboard
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
"With math, all things are possible." —Rebecca Watson
Re: Infinite queens on an infinite chessboard
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.

 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
I'm not a mathmind just yet, but if there are infinite Queens and infinite spaces, doesn't each space have a queen?
Re: Infinite queens on an infinite chessboard
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.
Re: Infinite queens on an infinite chessboard
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?
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?
Re: Infinite queens on an infinite chessboard
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.
Re: Infinite queens on an infinite chessboard
I feel stupid. Only now I have noticed that this is not equal to the nqueens 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:
Anyway I think this time I got the real solution:
I have even made a crappy OO.Calc macro to try it:
Spoiler:
Anyway I think this time I got the real solution:
Spoiler:
Re: Infinite queens on an infinite chessboard
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 currentlyfilled 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.
Re: Infinite queens on an infinite chessboard
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:
However with a little twerk:
Spoiler:
Re: Infinite queens on an infinite chessboard
userxp wrote:Anyway I think this time I got the real solution:Spoiler:
That's very nice, and it works. So the procedure is now:
Spoiler:
Re: Infinite queens on an infinite chessboard
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 2x1 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?
For clarification, If we have a finite square, then there are always 2x1 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.
Re: Infinite queens on an infinite chessboard
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 2x1 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.
Re: Infinite queens on an infinite chessboard
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.
Re: Infinite queens on an infinite chessboard
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.
Re: Infinite queens on an infinite chessboard
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 1to1 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 sizepreserving 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.
Re: Infinite queens on an infinite chessboard
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:
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.
Re: Infinite queens on an infinite chessboard
I came to the same solution as nitrodon did before reading the topic, it's defiantly the correct one,
Spoiler:

 Posts: 65
 Joined: Sun Jul 26, 2009 6:37 am UTC
Re: Infinite queens on an infinite chessboard
Here's a little insight into the problem:
Spoiler:
Spoiler:
Re: Infinite queens on an infinite chessboard
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 nonconstructive argument if we wellorder the lines on the chessboard. This will require the axiom of choice, which is equivalent to the wellordering principle, and the continuum hypothesis, to guarantee to each queen is preceded by only countably many queens, so a nonattacked 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.
(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.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Infinite queens on an infinite chessboard
Yes.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?
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 I_{0} and I_{1} of finite length such that each intersects X in a set of positive measure. Given I_{s} which intersects X in a set of positive measure, iteratively construct disjoint closed subintervals I_{s0} and I_{s1} such that each intersects X in a set of positive measure. In this way, we iteratively construct intervals I_{t} 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, I_{s} and I_{t} are disjoint.
For each s, let x_{s} be an element of [imath]I_s \cap X[/imath]. Given a sequence f of 0s and 1s, let x_{f} be a limit point of {x_{s} : s is an initial segment of f}. Since this set is bounded (it is a subset of I_{0} or I_{1}) 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 nplace initial segments of f and g, respectively. Then all but n1 elements of {x_{s} : s is an initial segment of f} are elements of I_{u}, so [imath]x_f \in I_u[/imath]. Similarly, [imath]x_g \in I_v[/imath]. Since I_{u} and I_{v} are disjoint, x_{f} and x_{g} are distinct. Thus {x_{f} : 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 wellorder has minimal type, so that no element has cmany 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
"With math, all things are possible." —Rebecca Watson
Re: Infinite queens on an infinite chessboard
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 nonempty.
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.
Who is online
Users browsing this forum: Yahoo [Bot] and 4 guests