Problem B. 5014. (March 2019)
B. 5014. After the elections in Nowhereland, there are \(\displaystyle 50 < n < 100\) representatives in the parliament, all from a single party called the Blue Party. (The Blue Party has a single president.) According to the law, a party in the parliament may be divided into two parties as long as the following conditions are met:
- The president of the old party is not allowed to become a member of the newly formed parties. His or her parliament mandate will terminate, thereby reducing the total number of representatives.
- Every other member may decide which new party to join.
- Each of the new parties must have at least one member among the representatives.
- Each of the new parties must elect a president from their representatives.
If at least one such splitting of a party results in all parties in the parliament having the same number of members, the parliament will be dissolved. What should be the value of \(\displaystyle n\) so that this could never happen?
(3 pont)
Deadline expired on April 10, 2019.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Tegyük fel, hogy \(\displaystyle k\geq 1\) pártszakadás után minden pártnak ugyanannyi, \(\displaystyle 1\leq a\) tagja van, és ezért a parlament feloszlatásra kerül. Minden pártszakadásnál 1-gyel csökken a mandátumok száma, vagyis \(\displaystyle k\) pártszakadás után össesen \(\displaystyle n-k\) képviselő lesz. A pártok száma mindig 1-gyel nő, így a végén \(\displaystyle k+1\) lesz, tehát
\(\displaystyle (k+1)a=n-k,\)
amiből
\(\displaystyle (k+1)(a+1)=n+1.\)
Tehát ha a parlamentet feloszlatják, akkor \(\displaystyle n+1\) felírható két 1-nél nagyobb egész szám szorzataként, következésképpen, ha \(\displaystyle n+1\) prím, akkor ez biztosan nem fordulhat elő.
Megmutatjuk, hogy ha \(\displaystyle n+1\) nem prím, akkor viszont előfordulhat, hogy a parlamentet feloszlatják. Mivel \(\displaystyle 1<n+1\), ezért ilyenkor \(\displaystyle n+1\) összetett szám, és felírható két 1-nél nagyobb egész szám szorzataként. Legyen ez a felbontás \(\displaystyle n+1=(k+1)(a+1)\). (Ekkor tehát \(\displaystyle a\) és \(\displaystyle k\) pozitív egész számok.) Megmutatjuk, hogy ilyenkor elérhető, hogy \(\displaystyle k\) pártszakadás után minden párt tagszáma \(\displaystyle a\) legyen (és így a parlament feloszlatásra kerüljön). Ezt úgy érjük el, hogy minden pártszakadásnál az egyik utódpárt mérete \(\displaystyle a\) lesz. Ekkor \(\displaystyle 0\leq i\leq k\) pártszakadás után lesz \(\displaystyle i\) darab \(\displaystyle a\) méretű párt, egy darab \(\displaystyle n-i(a+1)\) méretű (és \(\displaystyle i\) darab elveszett mandátum). Amíg \(\displaystyle i<k\), az \(\displaystyle n-i(a+1)\) méretű pártot tovább tudjuk osztani egy \(\displaystyle a\) méretűre és egy \(\displaystyle n-(i+1)(a+1)\) méretűre. Így eljárva a végén (\(\displaystyle i=k\) mellett) valóban minden párt \(\displaystyle a\) méretű lesz, hiszen \(\displaystyle n-k(a+1)=a\) teljesül \(\displaystyle n+1=(k+1)(a+1)\) miatt.
Ezzel beláttuk, hogy pontosan akkor nem fordulhat elő, hogy a parlamentet feloszlatják, ha \(\displaystyle n+1\) prímszám. Mivel \(\displaystyle n\in (50,100)\), ezért \(\displaystyle n+1\in (51,101)\). Az \(\displaystyle (51,101)\) intervallumba eső prímek:
\(\displaystyle 53,59,61,67,71,73,79,83,89,97.\)
Tehát \(\displaystyle n\) értéke \(\displaystyle 52,58,60,66,70,72,78,82,88,96\) lehet.
Statistics:
69 students sent a solution. 3 points: Ajtai Boglárka, Apagyi Dávid, Argay Zsolt, Beke Csongor, Bukva Dávid, Csaplár Viktor, Füredi Erik Benjámin, Győrffi Ádám György, Hegedűs Dániel, Horváth 721 Balázs, Horvath Csongor, Jánosik Áron, Jánosik Máté, Koleszár Domonkos, Kovács 129 Tamás, Lovas Márton, Nádor Benedek, Nagy 551 Levente, Nyitrai Boglárka, Sándor Péter, Szabó 991 Kornél, Szűcs 064 Tamás, Tálos Zoltán, Terjék András József, Tot Bagi Márton, Tóth 827 Balázs, Tóth Ábel, Tóth-Rohonyi Iván, Tubak Dániel, Zsigri Bálint. 2 points: 34 students. 1 point: 2 students. 0 point: 3 students.
Problems in Mathematics of KöMaL, March 2019