Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    7
    ReputationRep:
    Anyone with some hints to tackle this? I thought i was making some progress , but am back to square one

    https://bmos.ukmt.org.uk/home/bmo2-2015.pdf
    •  Official Rep
    Offline

    15
    ReputationRep:
     Official Rep
    Sorry you've not had any responses about this. Are you sure you've posted in the right place? Here's a link to our subject forum which should help get you more responses if you post there.

    You can also find the Exam Thread list for A-levels here and GCSE here. :dumbells:


    Just quoting in Fox Corner so she can move the thread if needed
    Spoiler:
    Show
    (Original post by Fox Corner)
    x
    • TSR Community Team
    Offline

    21
    ReputationRep:
    TSR Community Team
    moved this to the maths forum for you
    Offline

    1
    ReputationRep:
    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.
    Spoiler:
    Show
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by MadChickenMan)
    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.
    Spoiler:
    Show
    thanks man, thats a really neat solution
    Offline

    18
    ReputationRep:
    (Original post by MadChickenMan)
    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.
    Spoiler:
    Show
    Damn i cant see it mate.
    Mind reposting this?


    Posted from TSR Mobile
    Offline

    16
    ReputationRep:
    (Original post by MadChickenMan)
    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.
    Spoiler:
    Show
    Very impressive though this stuff is beyond me
    Offline

    1
    ReputationRep:
    (Original post by physicsmaths)
    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
    Offline

    12
    ReputationRep:
    (Original post by MadChickenMan)
    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
    Offline

    1
    ReputationRep:
    (Original post by drandy76)
    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

    \[ f((c,g,n)) =  \begin{cases}    (c,g',n)       & \quad \text{if } (c,g',n) \in C\times G\times N\\    (c,g,n)  & \quad \text{if } (c,g',n) \notin C\times G\times N\\  \end{cases}\]

    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.
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by MadChickenMan)
    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

    \[ f((c,g,n)) =  \begin{cases}    (c,g',n)       & \quad \text{if } (c,g',n) \in C\times G\times N\\    (c,g,n)  & \quad \text{if } (c,g',n) \notin C\times G\times N\\  \end{cases}\]

    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.
    the thing is i didn't even consider trying to make a mapping between the two sets - again very nice solution
    Offline

    18
    ReputationRep:
    (Original post by MadChickenMan)
    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

    \[ f((c,g,n)) =  \begin{cases}    (c,g',n)       & \quad \text{if } (c,g',n) \in C\times G\times N\\    (c,g,n)  & \quad \text{if } (c,g',n) \notin C\times G\times N\\  \end{cases}\]

    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.
    Very nice!
    Problems 3 and 4 kn this paper were better though


    Posted from TSR Mobile
 
 
 
Poll
Who is your favourite TV detective?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.