Bmo 2 2015, q2

If you're still having trouble, a common strategy for showing one set is bigger than another is to show there is an injective map between them.

I've left my solution if you wanted to take a look. I can't promise it's definitely correct.

If you're still having trouble, a common strategy for showing one set is bigger than another is to show there is an injective map between them.

I've left my solution if you wanted to take a look. I can't promise it's definitely correct.

If you're still having trouble, a common strategy for showing one set is bigger than another is to show there is an injective map between them.

I've left my solution if you wanted to take a look. I can't promise it's definitely correct.

Damn i cant see it mate.
Mind reposting this?


Posted from TSR Mobile

Here it is again. Let me know if you still can't see it.
BMO2 2015 Q2.pdf

Can't see it either time, probably an issue with the phone app


Posted from TSR Mobile

Typed it out on here, so hopefully you can see it now

We will show b) $\Rightarrow$ a) and then, since the contrapositive of a) $\Rightarrow$ b) is exactly the same argument, only interchanging boys and girls, this will suffice.

Denote each pupil by $p\in C\times G\times N$, where $C = \lbrace 1,2,\cdots,2m+1\rbrace$ denotes the class number, $G = \lbrace 0,1\rbrace$ denotes the gender ($0$ representing female) and $N = \lbrace 1,2,\cdots,n\rbrace$ denotes the $k^{\text{th}}$ female/male in a class. So $p=(3,1,5)$ means the $5^{\text{th}}$ male in the third class, for example.

Now define the function $f$, such that



Where $g'=1$ if $g=0$ and $g'=0$ if $g=1$.

For each way to form a school council out of an odd number of girls, apply the above function to each member of the school council, note that there is still exactly one member from each class. If the number of members unchanged by the function is even, because there are an odd number of classes, there must be an odd number of boys now. If the number was odd, then order the members by class number and then pick the member with the smallest $c$ that was not unchanged by the function and apply the function again (essentially reversing the change). Now there are an even number unchanged and so as before, an odd number of boys. It must be shown that the member with the smallest $c$ described above, can indeed be found. If it did not exist, then every member of the council would be unchanged by the function and so would have to belong to a class where there were more of their own gender. From the premise that there are an odd number of classes with more boys than girls, there must be an even number of girls, a contradiction.

This rather complex procedure induces a function on each version of the student council with an odd number of girls. The image of the function are the versions where there an odd number of boys. It suffices to check this function is injective. We can identify the members of the council that were unchanged by $f$, since being unchanged is equivalent to their number $n$ being greater than the number of members of the opposite gender in their class. This allows us to identify if another element was changed and then changed back and which it was. In this way, there is a natural inverse to this function, since we can recover the original student council with an odd number of girls. This shows the function is injective and because there are an odd number of ways to chose the council, there must be more ways to form the student council with an odd number of boys. So we are done.

Typed it out on here, so hopefully you can see it now

We will show b) $\Rightarrow$ a) and then, since the contrapositive of a) $\Rightarrow$ b) is exactly the same argument, only interchanging boys and girls, this will suffice.

Denote each pupil by $p\in C\times G\times N$, where $C = \lbrace 1,2,\cdots,2m+1\rbrace$ denotes the class number, $G = \lbrace 0,1\rbrace$ denotes the gender ($0$ representing female) and $N = \lbrace 1,2,\cdots,n\rbrace$ denotes the $k^{\text{th}}$ female/male in a class. So $p=(3,1,5)$ means the $5^{\text{th}}$ male in the third class, for example.

Now define the function $f$, such that



Where $g'=1$ if $g=0$ and $g'=0$ if $g=1$.

For each way to form a school council out of an odd number of girls, apply the above function to each member of the school council, note that there is still exactly one member from each class. If the number of members unchanged by the function is even, because there are an odd number of classes, there must be an odd number of boys now. If the number was odd, then order the members by class number and then pick the member with the smallest $c$ that was not unchanged by the function and apply the function again (essentially reversing the change). Now there are an even number unchanged and so as before, an odd number of boys. It must be shown that the member with the smallest $c$ described above, can indeed be found. If it did not exist, then every member of the council would be unchanged by the function and so would have to belong to a class where there were more of their own gender. From the premise that there are an odd number of classes with more boys than girls, there must be an even number of girls, a contradiction.

This rather complex procedure induces a function on each version of the student council with an odd number of girls. The image of the function are the versions where there an odd number of boys. It suffices to check this function is injective. We can identify the members of the council that were unchanged by $f$, since being unchanged is equivalent to their number $n$ being greater than the number of members of the opposite gender in their class. This allows us to identify if another element was changed and then changed back and which it was. In this way, there is a natural inverse to this function, since we can recover the original student council with an odd number of girls. This shows the function is injective and because there are an odd number of ways to chose the council, there must be more ways to form the student council with an odd number of boys. So we are done.