* * * SC2 Mafia Thread * * * -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Thread : ambassador problem https://www.sc2mafia.com/forum/showthread.php?t=47774 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 1] Auteur : yzb25 Date : November 20th, 2020 06:04 PM Title : 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 2] Auteur : Voss Date : November 20th, 2020 08:56 PM Title : Re: ambassador problem 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? -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 3] Auteur : yzb25 Date : November 21st, 2020 03:45 AM Title : Re: ambassador problem 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? 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: 27600 They divide neatly into two groups as you described, and we can apply your solution to seat them around the table: 27601 But there are other possible enemy structures. Like this one: 27602 So it cannot be taken for granted that they divide into two groups as described. For higher [X], other structures may emerge. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 4] Auteur : Renegade Date : November 21st, 2020 09:36 AM Title : Re: ambassador problem I'm working on this. Reminds me of the graceful coloring problem for trees. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 5] Auteur : DJarJar Date : November 21st, 2020 11:33 AM Title : 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 6] Auteur : MattZed Date : November 21st, 2020 01:54 PM Title : 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,8), (3,5), (3,6), (3,8), (4,7), (4,8), (5,7). Alternative solution I believe is correct: 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 7] Auteur : DJarJar Date : November 21st, 2020 09:58 PM Title : 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,8), (3,5), (3,6), (3,8), (4,7), (4,8), (5,7). Alternative solution I believe is correct: 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 8] Auteur : MattZed Date : November 21st, 2020 10:21 PM Title : Re: ambassador problem 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 9] Auteur : DJarJar Date : November 21st, 2020 11:47 PM Title : Re: ambassador problem 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. 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 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 10] Auteur : MattZed Date : November 22nd, 2020 12:07 AM Title : Re: ambassador problem (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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 11] Auteur : DJarJar Date : November 22nd, 2020 12:22 AM Title : Re: ambassador problem 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 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 12] Auteur : deathworlds Date : November 22nd, 2020 03:27 AM Title : Re: ambassador problem math -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 13] Auteur : yzb25 Date : November 22nd, 2020 03:48 AM Title : 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 14] Auteur : yzb25 Date : November 22nd, 2020 04:02 AM Title : Re: ambassador problem maybe I should put this in the first post. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 15] Auteur : Helz Date : November 22nd, 2020 05:03 PM Title : Re: ambassador problem This looks fun -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 16] Auteur : FrostByte Date : November 24th, 2020 02:01 AM Title : Re: ambassador problem 2 tables gg -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 17] Auteur : yzb25 Date : November 27th, 2020 01:59 PM Title : Re: ambassador problem 2 tables gg THE U.N. BUDGET DOES NOT ALLOW FOR THAT. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 18] Auteur : Marshmallow Marshall Date : November 27th, 2020 03:30 PM Title : Re: ambassador problem 2 tables gg THE U.N. BUDGET DOES NOT ALLOW FOR THAT. Can we please rep those posts to infinity -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 19] Auteur : Bruno Date : December 9th, 2020 08:00 PM Title : Re: ambassador problem 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. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-