My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

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


Reply
 
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 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.
wuzhe is offline  
 
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.
wuzhe is offline  
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.
Hoempa is offline  
June 20th, 2012, 04:24 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
wuzhe is offline  
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).
Hoempa is offline  
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.
Hoempa is offline  
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.
icemanfan is offline  
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
File Type: png 23 queens on 20x20 board.PNG (12.3 KB, 1662 views)
wuzhe is offline  
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
Denis is offline  
Reply

  My Math Forum > Math Forums > Math Events

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





Copyright © 2019 My Math Forum. All rights reserved.