ambassador problem
Register

User Tag List

Results 1 to 18 of 18
  1. #1

    ambassador problem

    there are 2 * [X] ambassadors. Each ambassador has [X] - 1 adversaries. Adversarial relationships are mutual, and ambassadors who are adversaries refuse to sit next to eachother.

    Thankfully, irrespective of who is who's adversary, you can always seat them around a round table in such a manner so that no ambassador sits next to one of their adversaries.

    why? how do you ensure this happens?

    (i.e. prove that there always exists a valid seating)

    UPDATE: I was expecting like one reply maybe I'm basically crying tears of joy rn.

    I apologize if the question was written opaquely. You must explain how a valid seating exists, irrespective of who is who's adversary - meaning every friend/enemy structure must be accounted for. Otherwise, Voss' solution also finds a valid seating for at least one friend/enemy structure for each X. Aamirus' proof elegantly lays out a way of breaking down a considerably larger number of cases though. From my own computations, it seems many are decomposable in the manner she described, but I honestly haven't considered X>4.

    Mattzed gives a correct outline of a proof and thus a correct answer. tbh, I was thinking about this one for a long ass time and never figured it out. So congrats! Of course, he's put it in spoilers, so I encourage anyone else interested to not view the solution and try it for yourself.
    Last edited by yzb25; November 22nd, 2020 at 04:02 AM.
    Quote Originally Posted by Blinkstorteddd02 View Post
    naz, he's claiming to have been at your house last night and infected you. I know u were drunk but PLEASE try as hard as you can to remember... That burning you felt the next morning when you went pee was from me, not him.

  2. #2

    Re: ambassador problem

    Spoiler : answer :
    You divide the ambassadors up into 2 groups, and within each group all the ambassadors are adversaries. This satisfies each ambassador having x - 1 adversaries. You then alternate seatings between group a and group b. Thus ambassadors only sit by people outside their group. and 2 times the amount of adversaries within each group satisfies the 2x ambassadors.


    I've not done mathematical proofs in ages, (and my answer isn't formal) but I think it makes sense?

    FM XVII: Bonney Jewelry (Journalist)
    FM XVIII: Kalou (Savage Godfather)
    FM XX: Joseph Bertrand (Marshall)
    FM XXI: USA (Escort)
    FM XV: Whiskey (Whore)

  3. #3

    Re: ambassador problem

    Quote Originally Posted by Voss View Post
    Spoiler : answer :
    You divide the ambassadors up into 2 groups, and within each group all the ambassadors are adversaries. This satisfies each ambassador having x - 1 adversaries. You then alternate seatings between group a and group b. Thus ambassadors only sit by people outside their group. and 2 times the amount of adversaries within each group satisfies the 2x ambassadors.


    I've not done mathematical proofs in ages, (and my answer isn't formal) but I think it makes sense?
    Spoiler : :
    The answer has merit. For example, consider 6 ambassadors red, blue, yellow, green, pink and orange, each with 2 enemies. The 6 ambassadors could have the follow adverserial relationships:
    possible relationship.png

    They divide neatly into two groups as you described, and we can apply your solution to seat them around the table:
    solution for possible relationship.png

    But there are other possible enemy structures. Like this one:
    alternate relationship.png

    So it cannot be taken for granted that they divide into two groups as described. For higher [X], other structures may emerge.
    Quote Originally Posted by Blinkstorteddd02 View Post
    naz, he's claiming to have been at your house last night and infected you. I know u were drunk but PLEASE try as hard as you can to remember... That burning you felt the next morning when you went pee was from me, not him.

  4. #4

  5. #5

    Re: ambassador problem

    Base Case:
    N=2, 4 nodes with each having 2 (n) friends and 1 (n-1) enemy.

    Let A have friends B and C, enemy D.
    Note that B and C cannot be friends, or else D would have 3 enemies. Therefore B and C are enemies and each are friends with D.
    Hence we can make a circle of ABDC.


    Assume the statement holds true for N-1. Then we already have a nice happy cycle like ABDC for 2(N-1) nodes. Each of these existing nodes has N-1 friends and N-2 enemies.

    For N, with 2 additional nodes being added, all nodes need to have N friends and N-1 enemies. Therefore, since all the existing nodes need to gain 1 enemy, it is impossible for the 2 new nodes to be enemies of each other (as the pre-existing 2(n-1) nodes uses up the n-1 enemies for each of the new nodes). So we can assume the 2 new nodes are friends, and therefore we can seat them next to each other and just need to find a spot in the existing circle to stick them in.

    We know for each existing node that it had to gain 1 friend and 1 enemy between the 2 new nodes. So for any arbitrary existing pair of friends, say AB, we have 2 cases:
    Case 1: One of them becomes friends with Y and enemies with Z, the other becomes friends with Z and enemies with Y. Then we can put the new pair YZ right here in the circle and we are done.

    Case 2: They both become friends with one of the new nodes and enemies with the other. WLOG let's say they both became friends with Y and enemies with Z. Then we can iterate around the circle. Look now at BC. If C became friends with Z then we are back to Case 1 and we are done. If C became friends with Y then keep going. We can repeat this at most N-1 times until all of Z's enemies are used up. Then it is guaranteed the next node will have to be friends with Z, so we are in case 1 and done.

    By induction it works for all N>=2.
    QED.
    Have you ever heard the tragedy of Darth Jar Jar the wise?

  6. #6

    Re: ambassador problem

    @aamirus , not every arrangement of 2x ambassadors can be reduced to a case of 2(x-1) ambassadors by removing two ambassadors. Consider the case of 8 ambassadors, where the pairs of rivals are (1,4), (1,7), (1,6), (2,5), (2,6), (2,, (3,5), (3,6), (3,, (4,7), (4,, (5,7).

    Alternative solution I believe is correct:

    Spoiler : solution :
    To get a seating arrangement, first seat everyone randomly. If no rivals are next to each other, we're done. If not, there exists rivals A and B such that B is sitting to the right of A. We want to "swap" B with one of A's non-rivals, C, such that the person to the right of C, (call this person D) is not a rival of B. Such a C always exists because A has x non-rivals and B only has x-1 rivals.

    Here's how we do the swap:

    Starting from A and looking right, we have something like ABXYZCD, where we know A is rivals with B, but B is not rivals with D and A is not rivals with C. If we reverse the order of everyone between A and D, we get something like ACZYXBD. Now, B is next to one fewer rivals, and C's number of adjacent rivals didn't increase. (they're still next to Z, and A isn't a rival, but we don't know if D was). Thus, we've decreased the number of rivals sitting next to each other by 1. (if C and D weren't rivals) or by 2 (if C and D were rivals).

    We repeat this process until there are no more rivals sitting next to each other.

    Quote Originally Posted by Arrow View Post
    What. You got me. Stop unvoting and stretch my neck, dammit.

  7. #7

    Re: ambassador problem

    Quote Originally Posted by MattZed View Post
    @aamirus , not every arrangement of 2x ambassadors can be reduced to a case of 2(x-1) ambassadors by removing two ambassadors. Consider the case of 8 ambassadors, where the pairs of rivals are (1,4), (1,7), (1,6), (2,5), (2,6), (2,, (3,5), (3,6), (3,, (4,7), (4,, (5,7).

    Alternative solution I believe is correct:

    Spoiler : solution :
    To get a seating arrangement, first seat everyone randomly. If no rivals are next to each other, we're done. If not, there exists rivals A and B such that B is sitting to the right of A. We want to "swap" B with one of A's non-rivals, C, such that the person to the right of C, (call this person D) is not a rival of B. Such a C always exists because A has x non-rivals and B only has x-1 rivals.

    Here's how we do the swap:

    Starting from A and looking right, we have something like ABXYZCD, where we know A is rivals with B, but B is not rivals with D and A is not rivals with C. If we reverse the order of everyone between A and D, we get something like ACZYXBD. Now, B is next to one fewer rivals, and C's number of adjacent rivals didn't increase. (they're still next to Z, and A isn't a rival, but we don't know if D was). Thus, we've decreased the number of rivals sitting next to each other by 1. (if C and D weren't rivals) or by 2 (if C and D were rivals).

    We repeat this process until there are no more rivals sitting next to each other.

    Thatís not relevant. He asked to prove only that there is at least 1 valid seating arrangement and Iíve given a valid inductive proof to show this. With induction we show that it works for a base case, and also that if it already works for N, it will also work for n+1. With these two facts combined you have proven that it works for all N greater than or equal to the base case. There might be valid seating arrangements you couldnít make using my construction but the point of the question was to guarantee at least 1 valid seating arrangement exists.
    Have you ever heard the tragedy of Darth Jar Jar the wise?

  8. #8

    Re: ambassador problem

    Quote Originally Posted by aamirus View Post
    Thatís not relevant. He asked to prove only that there is at least 1 valid seating arrangement and Iíve given a valid inductive proof to show this. With induction we show that it works for a base case, and also that if it already works for N, it will also work for n+1. With these two facts combined you have proven that it works for all N greater than or equal to the base case. There might be valid seating arrangements you couldnít make using my construction but the point of the question was to guarantee at least 1 valid seating arrangement exists.
    Mate, I'm saying your inductive step isn't valid. Not every collection of 2N ambassadors with N-1 rivals each can be viewed as adding two ambassadors to 2(N-1) ambassadors who each have N-2 rivals.
    Quote Originally Posted by Arrow View Post
    What. You got me. Stop unvoting and stretch my neck, dammit.

  9. #9

    Re: ambassador problem

    Quote Originally Posted by MattZed View Post
    Mate, I'm saying your inductive step isn't valid. Not every collection of 2N ambassadors with N-1 rivals each can be viewed as adding two ambassadors to 2(N-1) ambassadors who each have N-2 rivals.
    Quote Originally Posted by yzb25 View Post
    prove that there always exists a valid seating
    Again, need at least one for any X, and I proved you could get at least one
    Have you ever heard the tragedy of Darth Jar Jar the wise?

  10. #10

    Re: ambassador problem

    Quote Originally Posted by yzb25 View Post
    (i.e. prove that there always exists a valid seating)
    @aamirus , you've shown SOME groups of 2X ambassadors with X-1 rivals have a valid seating. You haven't shown all of them.

    Again, not *every* group of 2X ambassadors with X-1 rivals each can be obtained by adding two ambassadors to a group of 2X-2 ambassadors where every ambassador has X-2 rivals.
    Quote Originally Posted by Arrow View Post
    What. You got me. Stop unvoting and stretch my neck, dammit.

  11. #11

    Re: ambassador problem

    Quote Originally Posted by MattZed View Post
    @aamirus , you've shown SOME groups of 2X ambassadors with X-1 rivals have a valid seating. You haven't shown all of them.

    Again, not *every* group of 2X ambassadors with X-1 rivals each can be obtained by adding two ambassadors to a group of 2X-2 ambassadors where every ambassador has X-2 rivals.
    If I’ve interpreted his question wrong, fair enough. Your proof would be more rigorous if proving the statement “there is always such a c” (similar to my case 2) and using N nodes instead of 7 for your reversal process. And showing after the first swap/reversal that you can still get such a C. So if that was the question then I’d say mine is invalid but yours is still not really an acceptable proof
    Last edited by aamirus; November 22nd, 2020 at 12:24 AM.
    Have you ever heard the tragedy of Darth Jar Jar the wise?

  12. #12

    Re: ambassador problem

    math
    Quote Originally Posted by MattZed View Post
    deathworld's and RLVG's suicides made me lul. I take a lot of pleasure in knowing that I gave you an night action, and that you used it to kill yourself.
    Quote Originally Posted by yzb25 View Post
    At least Mesk has lewdy lefty and raunchy righty. You're not even Canadian.
    Quote Originally Posted by Unknown1234 View Post
    BRO HUUUUUUMP!! That's so Mesk.
    Quote Originally Posted by Stealthbomber16 View Post
    fucketh me in the ass

  13. #13

    Re: ambassador problem

    I was expecting like one reply maybe I'm basically crying tears of joy rn.

    I apologize if the question was written opaquely. You must explain how a valid seating exists, irrespective of who is who's adversary - meaning every friend/enemy structure must be accounted for. Otherwise, Voss' solution also finds a valid seating for at least one friend/enemy structure for each X. Aamirus' proof elegantly lays out a way of breaking down a considerably larger number of cases though. From my own computations, it seems many are decomposable in the manner she described, but I honestly haven't considered X>4.

    Mattzed gives a correct outline of a proof and thus a correct answer. tbh, I was thinking about this one for a long ass time and never figured it out. So congrats! Of course, he's put it in spoilers, so I encourage anyone else interested to not view the solution and try it for yourself.
    Quote Originally Posted by Blinkstorteddd02 View Post
    naz, he's claiming to have been at your house last night and infected you. I know u were drunk but PLEASE try as hard as you can to remember... That burning you felt the next morning when you went pee was from me, not him.

  14. #14

    Re: ambassador problem

    maybe I should put this in the first post.
    Quote Originally Posted by Blinkstorteddd02 View Post
    naz, he's claiming to have been at your house last night and infected you. I know u were drunk but PLEASE try as hard as you can to remember... That burning you felt the next morning when you went pee was from me, not him.

  15. #15

  16. #16

  17. #17

    Re: ambassador problem

    Quote Originally Posted by FrostByte View Post
    2 tables

    gg
    THE U.N. BUDGET DOES NOT ALLOW FOR THAT.
    Quote Originally Posted by Blinkstorteddd02 View Post
    naz, he's claiming to have been at your house last night and infected you. I know u were drunk but PLEASE try as hard as you can to remember... That burning you felt the next morning when you went pee was from me, not him.

  18. #18

    Re: ambassador problem

    Quote Originally Posted by FrostByte View Post
    2 tables

    gg
    Quote Originally Posted by yzb25 View Post
    THE U.N. BUDGET DOES NOT ALLOW FOR THAT.
    Can we please rep those posts to infinity
    Spoiler : Quotes :
    Quote Originally Posted by S-FM Hey peter View Post
    There are two wolves inside you. One is addicted to crack. The other one is also addicted to crack. You are addicted to crack.
    Quote Originally Posted by Stealthbomber16 View Post
    MM IS AN ANTI-VAXXER
    Quote Originally Posted by BananaCucho View Post
    Mallow are you really an anti vaxxer
    Quote Originally Posted by The Lawyer View Post
    Besides your lamp and your refridgerators, do you find anyone else suspicious?
    Quote Originally Posted by Renegade View Post
    God is a goofy loser.

 

 

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •