My Math Forum a chessboard problem

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 April 24th, 2012, 12:57 PM #1 Senior Member   Joined: Jun 2011 Posts: 164 Thanks: 0 a chessboard problem I saw this problem from a Harvard-MIT math competition: given a 20x20 chessboard, place 25 queens on the board in a way that every queen attacks maximum of 1 other queen. For those who does not know how queen moves, they move horizontally, vertically, and diagonally of a unlimited amount of squares. The scoring will be done this way: If you get 20 queen on the board in a way that the question is described, you get 0 points, but for every extra queen you put on the board, you get 5 points. (meaning a totally possible of 25 points) Being a chess player, I am quite desperate to solve this , but I don't really have a good plan yet.
 June 20th, 2012, 10:24 AM #2 Senior Member   Joined: Jun 2011 Posts: 164 Thanks: 0 Re: a chessboard problem okay, it has been almost two months since i asked this, does anyone have a clue? If not, looks like I have to let this one go.
 June 20th, 2012, 03:22 PM #3 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 Re: a chessboard problem Place 20 queens on the board such that non of them attacks one another (If possible to do so, I didn't investigate that, but let's assume we can). Now, place #21. Now, it will attack at least one queen since it is on the same row as at least one of the others.
June 20th, 2012, 04:24 PM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: a chessboard problem

Quote:
 Originally Posted by Hoempa Now, it will attack at least one queen since it is on the same row as at least one of the others.
But that's allowed by the question.

June 21st, 2012, 06:40 AM   #5
Senior Member

Joined: Jun 2011

Posts: 164
Thanks: 0

Re: a chessboard problem

Quote:
 Originally Posted by Hoempa Place 20 queens on the board such that non of them attacks one another (If possible to do so, I didn't investigate that, but let's assume we can). Now, place #21. Now, it will attack at least one queen since it is on the same row as at least one of the others.
I am very glad that people started helping me with this problem, I appreciate it
That technique sounds good, the only problem is: Since the twenty queens attacks every row and every column (excluding diagonals for now), therefore every square other than the squares where you put the queens is attacked twice by two different queens. That makes the next move impossible because no matter where you place the queen, it will be under attack twice and also attacking two other queens, but that makes the statement of attacking 1 maximum other queen false.
I believe there are other ways or the answer is just impossible.

Also, it is not necessary to place 25 queens, you can place either less or more if possible.

And I am sorry that I forgot to mention that you are allowed not to answer the question if it is too difficult, but you are allowed to guess. As in the tournament, the 25-point questions are the most elite questions (because they are hardest and worth much more than others), each correct answer could affect the outcome of the competition. However, it is completely possible for the answer to be impossible because teams could waste precious amounts of time on it.

 June 21st, 2012, 01:06 PM #6 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 Re: a chessboard problem Sorry for misreading the Q. Your reasoning sounds good, but there might be something to look at. Since every queen may be attacked by a maximum of one other queen, you might place two queens in the same row. Now, placing 20 queens, it follows that some queens are attacked only once by row and columns (leaving the diagonals).
 June 22nd, 2012, 07:39 AM #7 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 Re: a chessboard problem Placing two queens on the same row doesn't change the conclusion. If you put a third on the same row or column where at least one of the queens already is, one queen is attacked more than once. To visualise, first place two queens on the same row Code: Q Q First case, third queen on same row as other two: Code: Q Q Q middle queen attacked twice which isn't allowed. Second case, third queen on same column as one of the queens. Code: Q Q Q Now, the queen initially in that column is attacked twice. Same of course for initially placing 2 queens in same column.
 June 26th, 2012, 01:14 PM #8 Senior Member   Joined: Feb 2012 Posts: 628 Thanks: 1 Re: a chessboard problem This is a board with 20 queens on it that satisfies the given conditions: QNNNNNNNNNNNNNNNNNNN NNNNNNNQNNNNNNNNNNNN NNNNNNNNNNNNNNQNNNNN NQNNNNNNNNNNNNNNNNNN NNNNNNNNQNNNNNNNNNNN NNNNNNNNNNNNNNNQNNNN NNQNNNNNNNNNNNNNNNNN NNNNNNNNNQNNNNNNNNNN NNNNNNNNNNNNNNNNQNNN NNNQNNNNNNNNNNNNNNNN NNNNNNNNNNQNNNNNNNNN NNNNNNNNNNNNNNNNNQNN NNNNQNNNNNNNNNNNNNNN NNNNNNNNNNNQNNNNNNNN NNNNNNNNNNNNNNNNNNQN NNNNNQNNNNNNNNNNNNNN NNNNNNNNNNNNQNNNNNNN NNNNNNNNNNNNNNNNNNNQ NNNNNNQNNNNNNNNNNNNN NNNNNNNNNNNNNQNNNNNN However, if you put another queen anywhere, it will be under attack by at least two others.
June 27th, 2012, 06:39 AM   #9
Senior Member

Joined: Jun 2011

Posts: 164
Thanks: 0

Re: a chessboard problem

Thanks for all the effort everyone put in, after searching through the web and asking friends and others about this question, I found out the answer was twenty-three queens placed on the board, (at least that is what the competition's answer gave, it also said "the best possible way is not known to us; the following construction gives 23", which means there is a possibility there could be more than 23 in the real answer
Attached Images
 23 queens on 20x20 board.PNG (12.3 KB, 1662 views)

 June 27th, 2012, 11:41 AM #10 Math Team   Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 14,326 Thanks: 1023 Re: a chessboard problem Somewhat similar to ye olde t trees in r rows puzzles; like 7 trees in 6 rows, 3 per rows: http://www.planetseed.com/node/18487

 Tags chessboard, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mpac Applied Math 0 June 16th, 2013 09:57 AM mathLover Applied Math 3 April 18th, 2012 10:42 AM wuzhe Algebra 1 August 11th, 2011 10:15 AM Gustav Number Theory 1 February 27th, 2011 08:04 AM jason.spade Math Events 4 May 17th, 2010 10:47 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top