
Math Events Math Events, Competitions, Meetups  Local, Regional, State, National, International 
 LinkBack  Thread Tools  Display Modes 
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 HarvardMIT 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:
 
June 21st, 2012, 06:40 AM  #5  
Senior Member Joined: Jun 2011 Posts: 164 Thanks: 0  Re: a chessboard problem Quote:
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 25point 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 Code: Q Q Q Second case, third queen on same column as one of the queens. Code: Q Q Q 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 twentythree 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

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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
chessboard partitions  mpac  Applied Math  0  June 16th, 2013 09:57 AM 
around the chessboard with a knight  mathLover  Applied Math  3  April 18th, 2012 10:42 AM 
a chessboard set up problem  wuzhe  Algebra  1  August 11th, 2011 10:15 AM 
Knight covers the chessboard  Gustav  Number Theory  1  February 27th, 2011 08:04 AM 
A Chessboard Problem  jason.spade  Math Events  4  May 17th, 2010 10:47 AM 