You are Here: Home >< Maths

The Proof is Trivial! Watch

1. (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
2. (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

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.
3. (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

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.
4. (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

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)
5. (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
6. (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?
7. (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=...queens&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
8. (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=...queens&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.
9. (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
10. (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.
11. (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.
12. (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).
13. Hopefully, you'll find this non-trivial...

Problem 496 **

Find all such that

for all integers satisfying
14. (Original post by Renzhi10122)
Hopefully, you'll find this non-trivial...

Find all such that

for all integers satisfying
Is it just the zero function? It's [f(x)]^2 not f(x^2) yes?
15. (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.
16. (Original post by Renzhi10122)
Hopefully, you'll find this non-trivial...

Find all such that

for all integers satisfying
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.
17. (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.
18. (Original post by Renzhi10122)
Hopefully, you'll find this non-trivial...
You have odd tastes - this is very messy Not sure I can be bothered to finish. Here is something interesting:

Given any , must there exist s.t.
19. (Original post by Lord of the Flies)
You have odd tastes - this is very messy Not sure I can be bothered to finish. Here is something interesting:

Given any , must there exist s.t.
Lol fair enough. (still a nice question though )

Ok, so
Spoiler:
Show
if we let y=0, and f(0)=a, then we need which essentially says that if for some x, then we are done. So we can now say that for all x. So, we then let x=0 to get .
If then let s.t. and and so if for positive b, then we are done.
If then let s.t. and . The same logic follows.
If then and for .
Thus, we can further restrict the we will deal with to those that for , and for , .

And that's me done for now.
20. (Original post by Renzhi10122)
Hopefully, you'll find this non-trivial...

Problem 496 **

Find all such that

for all integers satisfying
ISL 2012 A1

Knew it looked familiar

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 11, 2017
Today on TSR

Last-minute PS help

100s of personal statements examples here

Loneliness at uni

Discussions on TSR

• Latest
• See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

How to use LaTex

Writing equations the easy way

Study habits of A* students

Top tips from students who have already aced their exams

Chat with other maths applicants

Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.