BdMO National 2021 Secondary Problem 9

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm
BdMO National 2021 Secondary Problem 9

Unread post by Pro_GRMR » Sun Apr 11, 2021 9:36 pm

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $80$ Pokemon. Cynthia wants to catch as many of them as possible. However, she cannot catch any two Pokemon that are enemies with each other. After exploring around for a while, she makes the following two observations:
1. Every Pokemon in Victory Road is enemies with exactly two other Pokemon.
2. Due to her inability to catch Pokemon that are enemies with one another, the maximum number of Pokemon she can catch is equal to $n$.
What is the sum of all possible values of $n$?
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
Swapnil Barua
Posts:14
Joined:Tue Apr 13, 2021 2:55 pm

Re: BdMO National 2021 Secondary Problem 9

Unread post by Swapnil Barua » Tue Apr 13, 2021 3:03 pm

Choose 1 to 10 numbers
1,2,3 and 4,5,6 and 7,8,9 and 10 (1,2,3 and 4,5,6 and 7,8,9 every 3 of them are enemies with each other)
1 isn't enemy with 4, 2 isn't enemy with 5, 3 isn't enemy with 6, (all 6 here)
There are 7,8,9 and 10 left
From them you can take any 1 number with 10 (all 2 here)
2+6=8
Cynthia can take From 10 pokemons 8 (which aren't enemy)
From 110 pokemons 110×8÷10=88

User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm

Re: BdMO National 2021 Secondary Problem 9

Unread post by Pro_GRMR » Tue Apr 13, 2021 8:29 pm

Swapnil Barua wrote:
Tue Apr 13, 2021 3:03 pm
Choose 1 to 10 numbers
1,2,3 and 4,5,6 and 7,8,9 and 10 (1,2,3 and 4,5,6 and 7,8,9 every 3 of them are enemies with each other)
1 isn't enemy with 4, 2 isn't enemy with 5, 3 isn't enemy with 6, (all 6 here)
There are 7,8,9 and 10 left
From them you can take any 1 number with 10 (all 2 here)
2+6=8
Cynthia can take From 10 pokemons 8 (which aren't enemy)
From 110 pokemons 110×8÷10=88
You're misunderstanding the problem. The number of maximum pokemon is entirely dependent on how they are set as enemies ie. the graph. So, n can change depending on how the graph looks. And thus creating multiple values of $n$. Also, I don't quite understand how you're taking $8$ from $10$.
"When you change the way you look at things, the things you look at change." - Max Planck

User avatar
Swapnil Barua
Posts:14
Joined:Tue Apr 13, 2021 2:55 pm

Re: BdMO National 2021 Secondary Problem 9

Unread post by Swapnil Barua » Wed Apr 14, 2021 11:29 am

7,8,9 are enemies with each other
You can't take any of them
You must take 7,10 or 8,10 or 9,10( You can choose one pair)
I didn't take any multiple value
In the last there will be 2 pokemons left from 1-10
If you take 7,10 the remaining pokemons will be 8,9
and if you take 8,10 the remaining pokemons will be 7,9
same goes for 9,10( remaining 7,8)
You can't take 7,8 or,8,9 or 7,9 (enemies with each other)

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO National 2021 Secondary Problem 9

Unread post by Mehrab4226 » Wed Apr 14, 2021 9:37 pm

$\def\lf{\lfloor}$ $\def\rf{\rfloor}$
Before we start to calculate how many pokemon Cynthia can catch, we need to make some ideas clear.
  1. If we have a graph(not multigraph) with n vertices such that each vertex having degree $= 2$, the number of vertices we can choose such that no $2$ vertices share a common edge is $\lf{\frac{n}{2}}\rf$[Note the cycle the graph contains must-have $n$ vertices]
    Proof: Since the cycle must have $n$ vertices we can rearrange the whole graph in such a way that it looks like an $n-gon$. And the maximum number of vertices we can choose is the same as the total number of lines joining a blue line like the picture below( I am not sure what it is called but probably not a diagonal). So the maximum number of vertices we can choose is $\lf \frac{n}{2} \rf$
    Screenshot 2021-04-14 21.28.50.png
    Screenshot 2021-04-14 21.28.50.png (33.78KiB)Viewed 6783 times
  2. A graph with the property in the question will have cycles with $3$ vertices, $4$ vertices all the way up to $n$ vertices[Not all of them in $1$ graph]. And the least number of vertices Cynthia can choose will depend on the arrangement of those cycles.
  3. The arrangement in which Cynthia can choose the least is the one containing the maximum number of $3-cycle$ graphs because $\lf\frac{k}{2}\rf +\lf \frac{n}{2}\rf \leq \lf \frac{n+k}{2} \rf $. In a graph of $80$, there can be a maximum of $25$ $3-cycle$ graphs and a $5-cycle$ graph. So the total number of pokemon she will choose is $\lf \frac{3}{2}\rf +\cdots 25 times \cdots \lf \frac{3}{2} \rf + \lf \frac{5}{2} \rf =27.$
  4. The maximum number of pokemon/vertices Cyntia can catch is in a cycle with the maximum number of vertices which is an $80-cycle$ for this case. So the maximum number of pokemon she can catch $\lf \frac{80}{2} \rf = 40$
  5. Finally she can catch any integer number of pokemon within $[27,40]$. She can catch those numbers if we take a few of the vertices of $cycle-3$ and add them up in $cycle-5$ or the cycle with the maximum vertices.
So the sum of all possible value of $n$ is $27+28+\cdots +39+40=469$(Ans) idk
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BdMO National 2021 Secondary Problem 9

Unread post by Asif Hossain » Thu Apr 22, 2021 2:32 pm

Mehrab4226 wrote:
Wed Apr 14, 2021 9:37 pm
$\def\lf{\lfloor}$ $\def\rf{\rfloor}$
Before we start to calculate how many pokemon Cynthia can catch, we need to make some ideas clear.
  1. If we have a graph(not multigraph) with n vertices such that each vertex having degree $= 2$, the number of vertices we can choose such that no $2$ vertices share a common edge is $\lf{\frac{n}{2}}\rf$[Note the cycle the graph contains must-have $n$ vertices]
    Proof: Since the cycle must have $n$ vertices we can rearrange the whole graph in such a way that it looks like an $n-gon$. And the maximum number of vertices we can choose is the same as the total number of lines joining a blue line like the picture below( I am not sure what it is called but probably not a diagonal). So the maximum number of vertices we can choose is $\lf \frac{n}{2} \rf$
    Screenshot 2021-04-14 21.28.50.png
  2. A graph with the property in the question will have cycles with $3$ vertices, $4$ vertices all the way up to $n$ vertices[Not all of them in $1$ graph]. And the least number of vertices Cynthia can choose will depend on the arrangement of those cycles.
  3. The arrangement in which Cynthia can choose the least is the one containing the maximum number of $3-cycle$ graphs because $\lf\frac{k}{2}\rf +\lf \frac{n}{2}\rf \leq \lf \frac{n+k}{2} \rf $. In a graph of $80$, there can be a maximum of $25$ $3-cycle$ graphs and a $5-cycle$ graph. So the total number of pokemon she will choose is $\lf \frac{3}{2}\rf +\cdots 25 times \cdots \lf \frac{3}{2} \rf + \lf \frac{5}{2} \rf =27.$
  4. The maximum number of pokemon/vertices Cyntia can catch is in a cycle with the maximum number of vertices which is an $80-cycle$ for this case. So the maximum number of pokemon she can catch $\lf \frac{80}{2} \rf = 40$
  5. Finally she can catch any integer number of pokemon within $[27,40]$. She can catch those numbers if we take a few of the vertices of $cycle-3$ and add them up in $cycle-5$ or the cycle with the maximum vertices.
So the sum of all possible value of $n$ is $27+28+\cdots +39+40=469$(Ans) idk
she can catch any integer number of pokemon within $[27,40]$. She can catch those numbers if we take a few of the vertices of $cycle-3$ and add them up in $cycle-5$ or the cycle with the maximum vertices. Elaborate pls :oops:
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO National 2021 Secondary Problem 9

Unread post by Mehrab4226 » Thu Apr 22, 2021 4:58 pm

Asif Hossain wrote:
Thu Apr 22, 2021 2:32 pm
Mehrab4226 wrote:
Wed Apr 14, 2021 9:37 pm
$\def\lf{\lfloor}$ $\def\rf{\rfloor}$
Before we start to calculate how many pokemon Cynthia can catch, we need to make some ideas clear.
  1. If we have a graph(not multigraph) with n vertices such that each vertex having degree $= 2$, the number of vertices we can choose such that no $2$ vertices share a common edge is $\lf{\frac{n}{2}}\rf$[Note the cycle the graph contains must-have $n$ vertices]
    Proof: Since the cycle must have $n$ vertices we can rearrange the whole graph in such a way that it looks like an $n-gon$. And the maximum number of vertices we can choose is the same as the total number of lines joining a blue line like the picture below( I am not sure what it is called but probably not a diagonal). So the maximum number of vertices we can choose is $\lf \frac{n}{2} \rf$
    Screenshot 2021-04-14 21.28.50.png
  2. A graph with the property in the question will have cycles with $3$ vertices, $4$ vertices all the way up to $n$ vertices[Not all of them in $1$ graph]. And the least number of vertices Cynthia can choose will depend on the arrangement of those cycles.
  3. The arrangement in which Cynthia can choose the least is the one containing the maximum number of $3-cycle$ graphs because $\lf\frac{k}{2}\rf +\lf \frac{n}{2}\rf \leq \lf \frac{n+k}{2} \rf $. In a graph of $80$, there can be a maximum of $25$ $3-cycle$ graphs and a $5-cycle$ graph. So the total number of pokemon she will choose is $\lf \frac{3}{2}\rf +\cdots 25 times \cdots \lf \frac{3}{2} \rf + \lf \frac{5}{2} \rf =27.$
  4. The maximum number of pokemon/vertices Cyntia can catch is in a cycle with the maximum number of vertices which is an $80-cycle$ for this case. So the maximum number of pokemon she can catch $\lf \frac{80}{2} \rf = 40$
  5. Finally she can catch any integer number of pokemon within $[27,40]$. She can catch those numbers if we take a few of the vertices of $cycle-3$ and add them up in $cycle-5$ or the cycle with the maximum vertices.
So the sum of all possible value of $n$ is $27+28+\cdots +39+40=469$(Ans) idk
she can catch any integer number of pokemon within $[27,40]$. She can catch those numbers if we take a few of the vertices of $cycle-3$ and add them up in $cycle-5$ or the cycle with the maximum vertices. Elaborate pls :oops:
At first we can agree,
$\lf \frac{3}{2}\rf +\cdots 25 times \cdots \lf \frac{3}{2} \rf + \lf \frac{5}{2} \rf =27$
Now this is the condition when there is $25$ cycle-3(cycle with 3 vertices) and $1$ cycle-5(Cycle with 5 vertices). Now if we take a 3 vertices from a single cycle-3 and add them in the cycle-5 this will make a cycle-8. So we have $24$ cycle-3 and $1$ cycle-8.
So the total number of pokemon Cynthia can catch is $1\times 24+4=28$
We can do similar steps again and get,
$23$ cycle-3 and $1$ cycle-11, which makes the number of pokemon $23+5=28$
Do the same again and we'll get $22+7=29$.
In this way, we can get all the numbers between 27 and 40 inclusive.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply