Disjuncte deelverzamelingen waarvan de sommen van de elementen gelijk zijn

Ik worstel met het volgende probleem.

Gegeven S als de verzameling van k gehele getallen {1990, 1991, 1992,...,1990 + k}. Kan deze verzameling voor alle k worden opgesplitst in twee disjuncte deelverzamelingen A en B zo dat de sommen van de elementen van A en B gelijk zijn? Als k=1+4n of 2+4n (n als natuurlijk getal) kan het niet, omdat de totale som dan steeds oneven is. Als k=3+4n kan het wel, omdat het probleem dan steeds is te reduceren tot n+1 deelprobleempjes van de vorm {1990+4n,1990+1+4n,1990+2+4n,1990+3+4n} waarbij de som van het eerste en het laatste element gelijk is aan de som van het tweede en het derde element.

Blijft over het geval k=1+4n. Volgens mij kan het wel, alleen voor hele grote n. Bij verzamelingen die beginnen met een kleiner getal zie je namelijk het volgende gebeuren (de verzameling begint altijd met een even getal en bestaat uit een vijfvoud elementen): voor een verzameling {2,3,4,5,6} kan het wel, voor de verzameling {4,5,6,7,8} kan het ook, voor de verzameling {6,7,8,9,10} niet meer. Voor de verzameling {6,7,8,9,10,11,12,13,14} kan het echter wel weer.

Voor de verzameling {1990,1991,1992,...,k heel groot} zou het dus ook moeten kunnen. Kan iemand hier iets zinnigs over zeggen m.b.t. de logica en/of een bewijsvoering geven dat het bij bepaalde k wel en bepaalde k niet kan?

Alvast mijn dank.

marc w
Student universiteit - woensdag 29 oktober 2003

Antwoord

Hoi,

Er staan een paar onnauwkeurigheden in je vraag. Daarom misschien een andere formulering: We bekijken de rij van m opeenvolgende natuurlijke getallen, beginnend met n: n, n+1, .., n+m-1. We proberen deze getallen in twee partities te groeperen, zodat de som van alle elementen van elke partitie gelijk is.

De som van al deze getallen is S=(n+m).(n+m-1)/2-n.(n-1)/2=n.m+m.(m-1)/2.



In het tabelletje bekijken we of S even is of oneven in functie van m(mod 4) en n(mod 2). Wanneer S oneven is, is de partitionering in 2 verzamelingen met gelijke som onmogelijk. We bekijken de andere gevallen:

Geval 1. m=0(mod 4)
We groeperen de getallen in koppels (n+i-1,n+m-i) met i=1..m/2. Voor elk koppel is de som steeds 2n+m-1 en er zijn zo m/2 koppels van twee verschillende getallen. Omdat m=0(mod 4), is m/2 even. Een mogelijke verdeling bestaat er dus in om de helft van de koppels in een eerste verzameling en de andere helft in een tweede verzameling te stoppen.

Geval 2. m=3(mod 4) en n=1(mod 2)
Net als in Geval 1 groeperen we in koppels (n+i-1,n+m-i) met i=1..(m-1)/2. We hebben zo (m-1)/2 koppels en het middelste getal n+(m-1)/2 blijft ongekoppeld over. Aangezien m=3(mod 4), is (m-1)/2 oneven.
We onderzoeken onder welke voorwaarden we een koppel (n+k-1,n+m-k) kunnen hercombineren met n+(m-1)/2 zodat we een goede partitionering krijgen van deze drie elementen. Omdat n+k-1 n+m-k, is de enige mogelijkheid: (n+k-1)+(n+(m-1)/2)= (n+m-k), waaruit: k=(m-2n+3)/4. Deze waarde voor k is geheel en zit tussen 1 en (m-1)/2 wanneer m2n+1. Onder deze voorwaarde bestaat er dus telkens een koppel dat we met het middelste element kunnen combineren tot twee verzamelingen met gelijke som.
De helft van de overige (m-3)/2 koppels voegen we bij {n+k-1, n+(m-1)/2} en de andere helft bij {n+m-k}.

Geval 3. m=1(mod 4) en n=0(mod 2)
We verdelen weer in koppels (n+i-1,n+m-i) met i=1..(m-1)/2. We hebben weer (m-1)/2 koppels van verschillende getallen en het middelste getal n+(m-1)/2 blijft ongekoppeld over.
Aangezien m=1(mod 4), is (m-1)/2 even.
We onderzoeken daarom of we twee koppels (n+k₁-1,n+m-k₁) en (n+k₂-1,n+m-k₂) (met k₁ k₂) kunnen hercombineren met n+(m-1)/2 tot een goede partitionering. De resterende (m-5)/2 koppels, een even aantal, kunnen we dan weer aanvullen zoals in de andere gevallen.

Er zijn twee manieren om te combineren:
Geval 3.1.
{n+k₁-1, n+m-k₂} en {n+m-k₁, n+k₂-1}.
De linkersom is 2n+m-( k₂- k₁)-1 en de rechtersom 2n+m+( k₂- k₁)-1. Aangezien k₁ k₂, moeten we n+(m-1)/2 dus links toevoegen. We krijgen gelijke sommen wanneer k₂- k₁=(2n+m-1)/4. Voor waarden van k₁ en k₂ tussen 1 en (m-1)/2 is het verschil maximaal (m-3)/2. Er zijn dus enkel oplossingen wanneer (2n+m-1)/4(m-3)/2 of m2n+2.

Geval 3.2.
{n+k₁-1, n+k₂-1} en {n+m-k₁, n+m-k₂}
Beide elementen in de linkerverzameling zijn kleiner dan n+(m-1)/2, terwijl die van de rechterverzameling groter zijn dan n+(m-1)/2. Daarom moeten we n+(m-1)/2 links toevoegen.
De voorwaarde wordt: k₁+ k₂=(3m-2n+5)/4. Uit de boven- en ondergrenzen voor k₁ en k₂ leiden we hier ook een ondergrens voor m in functie van n af.

Conclusie:
m=0(mod 4) : altijd mogelijk
m=3(mod 4) en n=1(mod 2) : altijd mogelijk voor voldoende grote m
m=1(mod 4) en n=0(mod 2) : altijd mogelijk voor voldoende grote m
andere gevallen van m en n : nooit mogelijk

Te onderzoeken:
Bestaat er een manier om in gevallen 2 en 3 ook een oplossing te vinden voor kleinere m?
Kunnen we bewijzen dat er voor sommige m geen oplossing bestaat?

Groetjes,
Johan

andros
woensdag 12 november 2003

Re: Disjuncte deelverzamelingen waarvan de sommen van de elementen gelijk zijn

©2001-2024 WisFaq