User Tag List

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.

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?

Originally Posted by Voss
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.

I'm working on this. Reminds me of the graceful coloring problem for trees.

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.

@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.

Originally Posted by MattZed
@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.

Originally Posted by aamirus
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.

Originally Posted by MattZed
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.
Originally Posted by yzb25
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

Originally Posted by yzb25
(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.

Originally Posted by MattZed
@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

math

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.

maybe I should put this in the first post.

This looks fun

2 tables

gg

Originally Posted by FrostByte
2 tables

gg
THE U.N. BUDGET DOES NOT ALLOW FOR THAT.

Originally Posted by FrostByte
2 tables

gg
Originally Posted by yzb25
THE U.N. BUDGET DOES NOT ALLOW FOR THAT.
Can we please rep those posts to infinity

That was like 5:00 in Moscow. I awakened by screams under my window. I seen some fight, nearly 4-5 ppl involved. First thing I did is called police. I am glad that that was just some drunk idiots, noone hurted seriously or killed. But my sleep was broken. I lie down, but I cannot sleep again, my head was like cracked with hammer with this rude awakening. I went too see what's going on here. First thing I seen is 6 votes on Baker with 4 of them townie for me. I said for myself "fuck it" and eneded that shit, push my PC off and go back to sleep, while policemen packaged that drunk guys under my window. Then silence comes, I slept for 8 hours nearly after.

Posting Permissions

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