The Student Room Group

The Proof is Trivial!

Scroll to see replies

Original post by Llewellyn
Are you sure this is the question you intended to ask? I remember a (very good) similar case where you were placing n black and n white queens on an infinite board such that no black piece can take a white piece and vice versa. Did you mean to ask this?

Otherwise I'm just getting n=3, simply by the fact that one queen must be the furthest left and the furthest down, thereby meaning it can at most interact with 3 other pieces (right, right/up diagonal and up). Unless I'm misreading this at 5am


Yes, I did mean that question. What about n=4 (I can't actually remember if this works or not)?

For your question, it should work for all n. You can place queens far enough apart so that they do not attack any other queen. (this probably isn't the question you were thinking of though, any chance you could share that problem?)

Posted from TSR Mobile
(edited 8 years ago)
Original post by Renzhi10122
Yes, I did mean that question. What about n=4 (I can't actually remember if this works or not)?

For your question, it should work for all n. You can place queens far enough apart so that they do not attack any other queen. (this probably isn't the question you were thinking of though, any chance you could share that problem?)

Posted from TSR Mobile

Yes, it occured to me that n=4 works for all boards larger than 3x3, that was stupid on my part :smile:

I'll ask my brother because I'm pretty sure he originally showed me the question. The point is that you have an m by m square board, and you place n black queens and n white queens such that no black or white can attack each other. You then find the maximum 'density' (2n/m) that can be achieved.

So a trivial solution to the above would be to place opposite coloured queens a knight's move away from each other. However this is not optimal.
Original post by Llewellyn
Yes, it occured to me that n=4 works for all boards larger than 3x3, that was stupid on my part :smile:

I'll ask my brother because I'm pretty sure he originally showed me the question. The point is that you have an m by m square board, and you place n black queens and n white queens such that no black or white can attack each other. You then find the maximum 'density' (2n/m) that can be achieved.

So a trivial solution to the above would be to place opposite coloured queens a knight's move away from each other. However this is not optimal.


Hmm, interesting question (btw, I think you mean 2n/(m^2) because 2n/m has no maximum), I'll have a think later.
Original post by Llewellyn
Yes, it occured to me that n=4 works for all boards larger than 3x3, that was stupid on my part :smile:

I'll ask my brother because I'm pretty sure he originally showed me the question. The point is that you have an m by m square board, and you place n black queens and n white queens such that no black or white can attack each other. You then find the maximum 'density' (2n/m) that can be achieved.

So a trivial solution to the above would be to place opposite coloured queens a knight's move away from each other. However this is not optimal.


The 'knight's solution has density 1/8 correct? (I'm not entirely sure what you mean)

There is a reasonable variation on the same theme that gives 2/9. Improving this seems pretty hard (for me)
(edited 8 years ago)
Original post by TheMagicMan
The 'knight's solution has density 1/8 correct? (I'm not entirely sure what you mean)

There is a reasonable variation on the same theme that gives 2/9. Improving this seems pretty hard (for me)

Yes, a lattice of points with (4x, 2y) black and (4x+2, 2y+1) white is 1/8. This is just an example of a solution, it's probably misleading to start from here.

I have got 1/4 so far, but I think I remember the limit being larger. I will check back when I don't still have exams
Original post by Llewellyn
Yes, a lattice of points with (4x, 2y) black and (4x+2, 2y+1) white is 1/8. This is just an example of a solution, it's probably misleading to start from here.

I have got 1/4 so far, but I think I remember the limit being larger. I will check back when I don't still have exams


If you iterate my method (which is essenitally to put in blocks of queens of the same colour with the blocks relating to each other in a knight like way) it can be improved to 16/63 in the limit, although that is barely more than 1/4. I think there are efficiencies that can be made by by reducing the diagonal footprint of each block i.e. to make a block look like
..X
XX
X

although I doubt you could get much better than 0.3 like that.

One way you could find a decent bound is to find a good solution for some m and then scaling up that solution. For example in the normal chessboard case 18 (n=9) is possible giving a density of ~0.28 so the optimal asymptotic density must be better than that.

The real challenge will be to find a good upper bound. I suspect 0.4 is easily an upper bound...any idea how to show that?

It would be nice to find some literature on this problem as I suspect it is somewhat beyond us. Any idea what the problem is called/ if it has a name?
(edited 8 years ago)
Original post by TheMagicMan
If you iterate my method (which is essenitally to put in blocks of queens of the same colour with the blocks relating to each other in a knight like way) it can be improved to 16/63 in the limit, although that is barely more than 1/4. I think there are efficiencies that can be made by by reducing the diagonal footprint of each block i.e. to make a block look like
..X
XX
X

although I doubt you could get much better than 0.3 like that.

One way you could find a decent bound is to find a good solution for some m and then scaling up that solution. For example in the normal chessboard case 18 (n=9) is possible giving a density of ~0.28 so the optimal asymptotic density must be better than that.

The real challenge will be to find a good upper bound. I suspect 0.4 is easily an upper bound...any idea how to show that?

It would be nice to find some literature on this problem as I suspect it is somewhat beyond us. Any idea what the problem is called/ if it has a name?

I feel like it is 3/7 (the upper bound). 1/2 also perhaps.

Searching is difficult because "chess problem" usually doesn't refer to maths, and the most common queen maths problem is just placing same coloured queens so they don't attack or placing knights of opposite colours.

I did find this: https://books.google.co.uk/books?id=fdgACAAAQBAJ&pg=PA271&lpg=PA271&dq=maximum+non+attacking+black+and+white+queens&source=bl&ots=viTe3X4IGF&sig=maMQT9WMUGza-HnRUnYmaKkN5KA&hl=en&sa=X&ei=Th9uVauHC4iu7gbT_YHoBA&ved=0CCcQ6AEwAQ#v=onepage&q=maximum%20non%20attacking%20black%20and%20white%20queens&f=false Which is also here http://ipg.host.cs.st-andrews.ac.uk/papers/spgW9.pdf
Which looks more promising than it likely is, they only run up to 12x12
(edited 8 years ago)
Original post by Llewellyn
I feel like it is 3/7 (the upper bound). 1/2 also perhaps.

Searching is difficult because "chess problem" usually doesn't refer to maths, and the most common queen maths problem is just placing same coloured queens so they don't attack or placing knights of opposite colours.

I did find this: https://books.google.co.uk/books?id=fdgACAAAQBAJ&pg=PA271&lpg=PA271&dq=maximum+non+attacking+black+and+white+queens&source=bl&ots=viTe3X4IGF&sig=maMQT9WMUGza-HnRUnYmaKkN5KA&hl=en&sa=X&ei=Th9uVauHC4iu7gbT_YHoBA&ved=0CCcQ6AEwAQ#v=onepage&q=maximum%20non%20attacking%20black%20and%20white%20queens&f=false Which is also here http://ipg.host.cs.st-andrews.ac.uk/papers/spgW9.pdf
Which looks more promising than it likely is, they only run up to 12x12


Do you know of any definitive upper bound?

Honestly it could even be 1, although that seems unlikely.
Original post by TheMagicMan
Do you know of any definitive upper bound?

Honestly it could even be 1, although that seems unlikely.


I remember solving something called the 8-Queens and investigating the n-queens problem as part of a programming course I took online some time back.

This *may* be of use to you, I'm not sure I fully understand the problem you are discussing.

http://mathworld.wolfram.com/QueensProblem.html
Original post by Zacken
I remember solving something called the 8-Queens and investigating the n-queens problem as part of a programming course I took online some time back.

This *may* be of use to you, I'm not sure I fully understand the problem you are discussing.

http://mathworld.wolfram.com/QueensProblem.html


Well, this is trivial compared to the problem they're discussing.
Original post by Zacken
I remember solving something called the 8-Queens and investigating the n-queens problem as part of a programming course I took online some time back.

This *may* be of use to you, I'm not sure I fully understand the problem you are discussing.

http://mathworld.wolfram.com/QueensProblem.html


Yeah that problem is pretty easy and probably not relevant. At this point I'm pretty much convinced that there is no good way to analytically approach this problem as it is equivalent to a constrained optimisation problem that is likely not explicitly solvable.
Original post by TheMagicMan
Yeah that problem is pretty easy and probably not relevant. At this point I'm pretty much convinced that there is no good way to analytically approach this problem as it is equivalent to a constrained optimisation problem that is likely not explicitly solvable.


This problems reminds me of optimal packing for spheres which gave mathemeticians some trouble (in fact, a formal proof of Kepler's conjecture was published this year).
Hopefully, you'll find this non-trivial...

Problem 496 **

Find all f:ZZ f: \mathbb{Z} \rightarrow \mathbb{Z} such that
f(a)2+f(b)2+f(c)2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a) f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a)
for all integers a,b,c a, b, c satisfying a+b+c=0 a+b+c=0
(edited 8 years ago)
Original post by Renzhi10122
Hopefully, you'll find this non-trivial...

Find all f:ZZ f: \mathbb{Z} \rightarrow \mathbb{Z} such that
f(a)2+f(b)2+f(c)2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a) f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a)
for all integers a,b,c a, b, c satisfying a+b+c=0 a+b+c=0


Is it just the zero function? It's [f(x)]^2 not f(x^2) yes?
Original post by jjpneed1
Is it just the zero function? It's [f(x)]^2 not f(x^2) yes?


Yeah, [f(x)]^2, and it's not just the zero function. Functions can be defined in parts.
Original post by Renzhi10122
Hopefully, you'll find this non-trivial...

Find all f:ZZ f: \mathbb{Z} \rightarrow \mathbb{Z} such that
f(a)2+f(b)2+f(c)2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a) f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a)
for all integers a,b,c a, b, c satisfying a+b+c=0 a+b+c=0


What background knowledge is assumed here (as per the usual difficulty rating outlined in the first post)? I have a few ideas, but as I've never properly learned how to solve functional equations I'll leave it if it requires specialist knowledge.
Original post by ThatPerson
What background knowledge is assumed here (as per the usual difficulty rating outlined in the first post)? I have a few ideas, but as I've never properly learned how to solve functional equations I'll leave it if it requires specialist knowledge.


Ah, I'll edit my post then, it shouldn't require any advanced methods.
(edited 8 years ago)
Original post by Renzhi10122
Hopefully, you'll find this non-trivial...


You have odd tastes - this is very messy :biggrin: Not sure I can be bothered to finish. Here is something interesting:

Given any f:  RRf:\;\mathbb{R}\to\mathbb{R}, must there exist x,yRx,y\in\mathbb{R} s.t. f(xf(y))>x+yf(x)?f\big( x-f(y)\big)>x+yf(x)?
Original post by Lord of the Flies
You have odd tastes - this is very messy :biggrin: Not sure I can be bothered to finish. Here is something interesting:

Given any f:  RRf:\;\mathbb{R}\to\mathbb{R}, must there exist x,yRx,y\in\mathbb{R} s.t. f(xf(y))>x+yf(x)?f\big( x-f(y)\big)>x+yf(x)?


Lol fair enough. (still a nice question though :smile: )

Ok, so

Spoiler

Original post by Renzhi10122
Hopefully, you'll find this non-trivial...

Problem 496 **

Find all f:ZZ f: \mathbb{Z} \rightarrow \mathbb{Z} such that
f(a)2+f(b)2+f(c)2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a) f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a)
for all integers a,b,c a, b, c satisfying a+b+c=0 a+b+c=0


ISL 2012 A1

Knew it looked familiar

Quick Reply