wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Political slugfest
        
(Message started by: ecoist on Nov 1^st, 2008, 9:22pm)

Title: Political slugfest
Post by ecoist on Nov 1^st, 2008, 9:22pm

4 libertarians, 13 republicans, and 17 democrats gather to argue their political philosophy. They wander about and debate each other in pairs. When two of them of different political persuasions debate each other, they become so disallusioned that they both change to the third political persuasion. Show that it cannot happen that, after awhile, all of them acquire the same political philosophy.

Title: Re: Political slugfest
Post by towr on Nov 2^nd, 2008, 8:29am

Reminds me of a type of lizard.. Let's see if I can find a link

Ah, here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1178217578;) we go, and more to the point, here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1049059077).

Title: Re: Political slugfest
Post by Hippo on Nov 2^nd, 2008, 2:09pm

let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif= e^{2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifi/3} be primitive 3rd root of unity.
Look at http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(l,r,d)=(lhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif+rhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif²+d)

Operations are additions of (-1,-1,2),(-1,2,-1) or (2,-1,-1) to (l,r,d).

As addition of (-1,-1,-1) does not change http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif, additional (0,0,3),(0,3,0) or (3,0,0) does not change http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(mod 3).

Starting position (4,13,17) is mod 3 equal (1,1,-1) having http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif= 1 (mod 3).
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(34,0,0) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif.
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,34,0) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif²
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,0,34) = 1

I am not able to finish the proof.

So try to go to 34d.
1) (4,13,17)+=(6,-3,-3)=(10,10,14)
2) (10,10,14)+=(-10,-10,20)=(0,0,34).

At least I have prooved noone else will be able ;).

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(12,13,14)=-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif+ 1 = ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 (mod 3) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(39,0,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,39,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,0,39)=0 (mod 3).
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(13,15,17)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif-1=-ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3(mod 3) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(45,0,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,45,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,0,45)=0 (mod 3).

If two of l,r,d are equal (mod 3), we can equalize them as in 1). Than convert to the remaining kind as in 2).
If l,r,d are distinct mod 3 we get http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(l,r,d) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3(mod 3) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(l+r+d,0,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,l+r+d,0)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif(0,0,l+r+d)=0 (mod 3).

Title: Re: Political slugfest
Post by towr on Nov 2^nd, 2008, 3:04pm

on 11/02/08 at 14:09:53, Hippo wrote:

So try to go to 34d.
1) (4,13,17)+=(6,-3,-3)=(10,10,14)
2) (10,10,14)+=(-10,-10,20)=(0,0,34).

That bodes well for Obama ;)

Title: Re: Political slugfest
Post by Eigenray on Nov 2^nd, 2008, 3:53pm

For the general case, the analysis is simpler if they're allowed to borrow people. For example, 3 libertarians left to themselves will stay libertarian. But after a couple rounds with a republican in the room (who then leaves, still a republican), they might just find themselves all democrats.

Find a simple criterion to determine whether one state can turn into another without borrowing.

Hippo: I also thought roots of unity were the right way to go. But they don't really work for a composite number of parties. That is, with n parties, and a given number of people, there are n^n-1 distinct states (allowing negative people), by looking at all the differences mod n. But http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif]/(n) has size n^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n)}, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif= e^{2pi i/n} is an n-th root of unity.

Title: Re: Political slugfest
Post by ecoist on Nov 2^nd, 2008, 5:27pm

I screwed up, guys! There is an elementary solution if the total number of people involved is a multiple of 3. I should have said there are only 3 libertarians.

Thinking about what Eigenray wrote, I came up with the following variation. Let there be 15 parties with the i-th party having i members, for i=1,...,15. Whenever 14 of these guys meet, no two belonging to the same party, they all switch to the party none belong to. Show that it cannot happen that after awhile everyone belongs to the same party.

Title: Re: Political slugfest
Post by Hippo on Nov 3^rd, 2008, 12:41am

on 11/02/08 at 15:53:53, Eigenray wrote:

Actually I didn't thing about general case and the roots of unity was used in confusing way ... I actualy thought on triangular grid mod 3. I have used 1,http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif² as a coordinates. You can as well use x,y,z space coordinates and project it to the plane perpendicular to main diagonal (t(1,1,1) line). ... There is 9 positions in the projection mod 3, 7 of them are on projections of axis. Mod 3 just projections of (1,-1,0) and (-1,1,0) are not.

I don't think it can be easily generalised to higher number of parties. At least not from my point of view :(. ...
Oh yes, it looks well for prime p number of parties, but I have had problems to imagine the mod p operation ;).

BTW: The greasmonkey eats spaces after escape sequences as http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif. How should it be avoided in posts?

Title: Re: Political slugfest
Post by ecoist on Nov 11^th, 2008, 4:27pm

Ok, how about this less ambitious generalization of the chameleon problem?

Suppose that there are n>2 political parties whose members satisfy two conditions.
a) For any two parties, the numbers of members of each party are incongruent modulo n.
b) If any n-1 people meet, no two of them belonging to the same party, then all n-1 switch to the party none belong to.
Show that it can never happen that everyone belongs to the same party.

Title: Re: Political slugfest
Post by ecoist on Nov 16^th, 2008, 11:44am

I'm a complete idiot (thx for letting me find out for myself)! This problem, and its generalization, belongs in easy. Wowbagger suggested the easy solution, and Hippo noted what was needed to be assumed to make his solution work.

The numbers of members of each party forms a multiset of residues modulo n. That multiset never changes when party switching occurs (see Hippo's example with (4,13,17). There are always exactly two parties with the same number of members modulo 3). The reason for this is that, when switching occurs, it amounts to subtracting 1 from each membership modulo n (adding n-1 members to one party's membership is the same as subtracting 1 modulo n). Hence, since initially all memberships are incongruent modulo n, they must remain incongruent modulo n; and so the guys can never all belong to the same party. The only way such a thing could happen is if, initially, n-1 memberships are congruent modulo n.