#Homework 18 Problem 5, Rebecca Embar

print(`This is Rebecca Embar's brilliant bijective proof of the fact that the number of Condorect scenarios with 2v-1 voters and 3 candidates`):
print(`equals 2*binomial(v+3,5)`):

read `C18.txt`:

#ComptoCond : given a positive integer v, generates the set of 
#compositions of v-2 into 6 parts, and turns each composition 
#into a vote-count-Condorcet scenario with 2*v-1 voters 

#vote-count-Condorcet scenarios are written in the following order
#[123,132,213,231,312,321]

ComptoCond := proc(v) local C,x,Cond,c:
	C := Comps(v-2,6):
	Cond := {}:
	
	#Each entry in C corresponds to the pair:
	#[(123,321),(231,132),(312,213),(123,231),(231,312),(123,312)]
	
	for c in C do
		Cond := Cond union {[1,0,0,1,1,0]+[c[1]+c[4]+c[6],c[2],c[3],c[2]+c[4]+c[5],c[3]+c[5]+c[6],c[1]]}:
	od:
	
	Cond:
end:

#CondtoComp : given a positive integer v, generates the set of
#vote-count-Condorcet scenarios with 2*v-1 voters and turns 
#each scenario into a decomposition of v-2 into 6 parts

CondtoComp := proc(v) local Cond,C,co,c4,c5,c6:
	Cond := Cond3G(2*v-1,[[0,1,1],[0,0,1]]):
	C := {}:
	
	for co in Cond do 
		co := co-[1,0,0,1,1,0]:
		c4 := (co[1]+co[4]-co[5]-co[6]-co[2]+co[3])/2:
		c5 := (co[4]+co[5]-co[1]-co[2]-co[3]+co[6])/2:
		c6 := (co[1]+co[5]-co[4]-co[6]-co[3]+co[2])/2:
		C := C union {[co[6],co[2],co[3],c4,c5,c6]}:
	od:
end:

#Proof:

#1 -> 2 iff 123+132+312 > 213+231+321 (1)
#2 -> 3 iff 231+213+123 > 321+312+132 (2)
#3 -> 1 iff 312+321+231 > 132+123+213 (3)

#(1)+(2) gives us 123 > 321 (4)
#(2)+(3) gives us 231 > 132 (5)
#(3)+(1) gives us 312 > 213 (6)

#This means that 123,231,312 are at least 1, and 
#123=231=312=1, 321=132=213=0 satisfies the (1),(2),(3)

#We then want to add the remaining 2*v-4 voters, while 
#maintaining the three inequalities.

#[(123,321),(231,132),(312,213),(123,231),(231,312),(123,312)]


#For every voter we add to 321, we must add one voter
#to 123 by (4), and similarly for 132 and 231, and 213
#and 312 by (5) and (6). Thus, we add y1 voters to 321 
#and 123, y2 voters to 132 and 231, and y3 voters to 213 
#and 312

#We now have that 123=321+1, 231=132+1, and 312=213+1.
#We cannot add any more voters to 321,132,213, but
#we can add more voters to 123,231,312. 

#To maintain (1), for every voter we add to 231 we must add 
#one voter to either 123 or 312. To maintain (2), for every
#voter we add to 312 we must add one voter to either 231
#or 123. To maintain (3), for every voter we add to 123 we must
#add one voter to either 312 or 231

#Thus, we add y4 voters to 231 and 123, y5 voters to 

#As the voters are added in pairs, [y1,y2,y3,y4,y5,y6] is a 
#composition of (2*v-4)/2 = v-2 into 6 parts.