Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    8
    ReputationRep:
    (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
    Offline

    4
    ReputationRep:
    (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.
    Offline

    8
    ReputationRep:
    (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.
    Offline

    3
    ReputationRep:
    (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)
    Offline

    4
    ReputationRep:
    (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
    Offline

    3
    ReputationRep:
    (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?
    Offline

    4
    ReputationRep:
    (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
    Offline

    3
    ReputationRep:
    (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.
    Online

    22
    ReputationRep:
    (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
    Offline

    8
    ReputationRep:
    (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.
    Offline

    3
    ReputationRep:
    (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.
    Offline

    8
    ReputationRep:
    (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).
    Offline

    8
    ReputationRep:
    Hopefully, you'll find this non-trivial...

    Problem 496 **

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

    2
    ReputationRep:
    (Original post by Renzhi10122)
    Hopefully, you'll find this non-trivial...

    Find all  f: \mathbb{Z} \rightarrow \mathbb{Z} such that
     f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2  f(b)f(c)+2f(c)f(a)
    for all integers  a, b, c satisfying  a+b+c=0
    Is it just the zero function? It's [f(x)]^2 not f(x^2) yes?
    Offline

    8
    ReputationRep:
    (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.
    Offline

    17
    ReputationRep:
    (Original post by Renzhi10122)
    Hopefully, you'll find this non-trivial...

    Find all  f: \mathbb{Z} \rightarrow \mathbb{Z} such that
     f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2  f(b)f(c)+2f(c)f(a)
    for all integers  a, b, c satisfying  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.
    Offline

    8
    ReputationRep:
    (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.
    Offline

    18
    ReputationRep:
    (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 f:\;\mathbb{R}\to\mathbb{R}, must there exist x,y\in\mathbb{R} s.t. f\big( x-f(y)\big)>x+yf(x)?
    Offline

    8
    ReputationRep:
    (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 f:\;\mathbb{R}\to\mathbb{R}, must there exist x,y\in\mathbb{R} s.t. f\big( x-f(y)\big)>x+yf(x)?
    Lol fair enough. (still a nice question though )

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

    And that's me done for now.
    Offline

    2
    ReputationRep:
    (Original post by Renzhi10122)
    Hopefully, you'll find this non-trivial...

    Problem 496 **

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

    Knew it looked familiar
 
 
 
  • 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
    Brussels sprouts
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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