wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Two Attacking Queens
        
(Message started by: THUDandBLUNDER on Oct 8^th, 2003, 4:48am)

Title: Two Attacking Queens
Post by THUDandBLUNDER on Oct 8^th, 2003, 4:48am

When two queens are randomly placed on an nxn chessboard the probability that they attack each other is 3/11.

What is n?

Title: Re: Two Attacking Queens
Post by BNC on Oct 8^th, 2003, 5:42am

Either I missed something, or it should be in "easy"...

::[hide]
A queen placed randomly on an nxn chessboard controles 3n-3 squares (I don't consider the square on which it stand "controlled")

The second queen may be placed on any of n^2-1 locations.

Solving 3(n-1)/(n^2-1)=3/11 gives n=1/10, so

n=10.
[/hide]::

What do you say?

Title: Re: Two Attacking Queens
Post by THUDandBLUNDER on Oct 8^th, 2003, 6:10am

Quote:

A queen placed randomly on an nxn chessboard controles 3n-3 squares

That is true only of queens placed randomly on the edge of the board.

Title: Re: Two Attacking Queens
Post by towr on Oct 8^th, 2003, 7:24am

It's pretty easy, I think.. the answer is ::[hide]11[/hide]::

Just a matter of finding the right formula and then find the n for which you get the given probability..

Title: Re: Two Attacking Queens
Post by THUDandBLUNDER on Oct 8^th, 2003, 9:21am

Quote:

Just a matter of finding the right formula

And how do you easily do that? I don't see the point in posting bald answers.

(I suppose the fact that the method is obvious makes it Easy.)

Title: Re: Two Attacking Queens
Post by towr on Oct 8^th, 2003, 10:55am

on 10/08/03 at 09:21:57, THUDandBLUNDER wrote:

And how do you easily do that? I don't see the point in posting bald answers.

(I suppose the fact that the method is obvious makes it Easy.)

The way I allways start is first looking at small problems, n=2, n=3, n=4. Once you see the regularity it's (in this case) easy enough to generalize it, and a math-program can help simplify it (though that's not even necessary)

Title: Re: Two Attacking Queens
Post by visitor on Oct 8^th, 2003, 11:08am

This may be taking it the long way around, but here goes.
[hide]
First figure the total number of squares attacked by a queen placed on every square of the board. That works out to
(n^2)*3(n-1)+ 2(n-2)^2+2(n-4)^2+2(n-6)^2... until n-? reaches 1 or 0. (Can that equation be simplified?)
Divide that by n^2 to get the average attacks.
Divide that by n^2 -1 to get the probability.
Then plugging different numbers in for n leads you to the correct solution.[/hide]

Title: Re: Two Attacking Queens
Post by James Fingas on Oct 8^th, 2003, 1:00pm

It's definitely possible to come up with a simpler formula. If you compute the answer for n=1 to 10 or so, you can find a pattern fairly easily. Hint: [hide]it doesn't grow exponentially.[/hide]

I factored out the 2n-2 squares that are covered horizontally, then the n-1 squares that are always covered diagonally, then assigned a number to each square on the board specifying how many squares more than those 3n-3 are covered. The sum of these values has a fairly simple formula.