Page 1 of 1

BdMO National 2021 Junior Problem 11

Posted: Mon Apr 12, 2021 1:06 pm
by Anindya Biswas
"সিনথিয়া পোকেমন পছন্দ করে এবং সে পারলে সবগুলো পোকেমনই ধরতে চায়। জয়ের রাস্তায় মোট \(50\)-টা পোকেমন আছে। সিনথিয়া এই পোকেমনগুলোর মধ্যে যত সম্ভব বেশি সংখ্যক পোকেমন ধরতে চায়। কিন্তু সে এমন দুটো পোকেমন কখনোই ধরতে পারবে না যারা পরস্পর শত্রু। কিছুক্ষণ ঘুরে বেড়ানোর পর সে নিচের দুটো জিনিস বুঝতে পারল।
  1. জয়ের রাস্তার প্রতিটা পোকেমনেরই ঠিক দুটো করে শত্রু আছে।
  2. যেহেতু সে পরস্পর শত্রু এমন দুটো পোকেমন কখনোই ধরতে পারবে না, তাই সে যতই চেষ্টা করুক না কেন, জয়ের রাস্তায় সে সর্বোচ্চ \(n\)-টা পোকেমন ধরতে পারবে।
\(n\)-এর সম্ভাব্য সব মানের যোগফল কত?"

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $50$ Pokemon. Cynthia wants to catch as many of them as possible. However, she can not 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 that she can catch is equal to $n$.
What is the sum of all possible values of $n$?

Re: BdMO National 2021 Junior Problem 11

Posted: Tue Aug 24, 2021 3:01 pm
by Anindya Biswas
Anindya Biswas wrote:
Mon Apr 12, 2021 1:06 pm
"সিনথিয়া পোকেমন পছন্দ করে এবং সে পারলে সবগুলো পোকেমনই ধরতে চায়। জয়ের রাস্তায় মোট \(50\)-টা পোকেমন আছে। সিনথিয়া এই পোকেমনগুলোর মধ্যে যত সম্ভব বেশি সংখ্যক পোকেমন ধরতে চায়। কিন্তু সে এমন দুটো পোকেমন কখনোই ধরতে পারবে না যারা পরস্পর শত্রু। কিছুক্ষণ ঘুরে বেড়ানোর পর সে নিচের দুটো জিনিস বুঝতে পারল।
  1. জয়ের রাস্তার প্রতিটা পোকেমনেরই ঠিক দুটো করে শত্রু আছে।
  2. যেহেতু সে পরস্পর শত্রু এমন দুটো পোকেমন কখনোই ধরতে পারবে না, তাই সে যতই চেষ্টা করুক না কেন, জয়ের রাস্তায় সে সর্বোচ্চ \(n\)-টা পোকেমন ধরতে পারবে।
\(n\)-এর সম্ভাব্য সব মানের যোগফল কত?"

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $50$ Pokemon. Cynthia wants to catch as many of them as possible. However, she can not 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 that she can catch is equal to $n$.
What is the sum of all possible values of $n$?
Let's consider the Pokemons as vertices in a graph $G$. Two vertex will be connected by an edge if and only if the corresponding pokemons are enemies of each other.
For the 1st condition, $G$ is a collection of connected components, where each component is only a cycle.
Let's assume the cycles are $C_1,C_2,C_3,\dots,C_k$ and cycle $C_i$ contains $a_i$ vertices.
So, $3\leq a_i\leq50$ for all $1\leq i\leq k$
And $a_1+a_2+a_3+\dots+a_k=50$
Let $q$ be the number of cycles that contains odd number of vertices.
Note that $q\in\{0,2,4,6,8,10,12,14,16\}$ and for each of them, there exists some valid configuration.
From $C_i$, she can choose maximum of $\lfloor\frac{a_i}{2}\rfloor$ pokemons.
So,
$n=\lfloor\frac{a_1}{2}\rfloor+\lfloor\frac{a_2}{2}\rfloor+\lfloor\frac{a_3}{2}\rfloor+\dots+\lfloor\frac{a_k}{2}\rfloor$
$\Rightarrow n=\frac{(a_1+a_2+a_3+\dots+a_k)-q}{2}$
$\Rightarrow n=25-\frac{q}2$
Sum of all such $n$,
$\boxed{S=25×9-\frac{8×9}{2}=189}$