WisFaq!

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

Hoi Andros,

Ik ben me nog steeds aan het verdiepen in het probleem en nu heb ik voor de situatie n(mod2)=0 en m(mod4)=1 het volgende verzonnen om de minimale m te bepalen waarvoor de verzameling getallen is op te splitsen in 2 partities waarvan de som gelijk is.

Situatie:
- rij van m opeenvolgende gehele getallen beginnend met getal n
- n(mod2)=0
- m(mod4)=1

De rij getallen is op te splitsen in de volgende 2 partities:]
P1={n,n+1,...,n+(m-1)/2}
P2={n+(m+1)/2,...,n+m-1}.

In P1 zitten dus (m+1)/2 getallen en in P2 zitten (m-1)/2 getallen, m.a.w. in P1 zit 1 getal meer dan in P2.

De som van de getallen uit P1 wordt S1=[(n+(m-1)/2)((n+(m+1)/2))-(n-1)n]/2
De totale som van P1 + P2 hadden we al bepaald als S2=nm+m(m-1)/2.

Door 2S1=S2 op te lossen vind je m=1+2(n)^(1/2), of iets anders geschreven m=1+2Wortel(n)
Zoek bij de gevonden m het kleinste getal, zeg x, groter of gelijk aan m waarvoor geldt x(mod4)=1 en je hebt volgens mij voor m=x de minimale m te pakken.

Waarschijnlijk kan voor geval 2 uit jouw oplossing op soortgelijke wijze de minimale m worden bepaald.

Ik ben tot bovenstaande aanpak gekomen door voor kleine n (n=2,4,6,8,10,12,14,16) de rijen uit te schrijven en te kijken voor welke m gepartitioneerd kan worden en verder door logisch redeneren. Het probleem is echter een sluitend bewijs te vinden en mijn oplossing te rechtvaardigen

Ik hoor graag je reactie op bovenstaande oplossing en ben benieuwd wat je er van vindt. Misschien kun je er nog iets aan toe voegen/een echt bewijs geven....

Groeten,
Marc

marc
27-11-2003

Antwoord

Hoi,

Je probeerde een vereenvoudigde opsplitsing voor een oneven aantal opeenvolgende getallen. De beperking n=0 (mod 2) en m=1 (mod 4) gebruikte je eigenlijk niet. Enkel m=1 (mod 2).

Je redenering dat 2.S₁=S₂ de voorwaarden voor m en n geeft, is correct. De uitdrukkingen voor S₁ en S₂ kloppen ook, en bij uitwerking vind ik inderdaad als voorwaarde: 4n=(m-1)² (dit is equivalent aan jouw uitdrukking).

De splitsing is dus enkel mogelijk als n=k² een kwadraat is en m=2k+1.

Je vindt dus inderdaad een oplossing voor een kleinere waarde van m dan via de methode die ik gebruikte (gevallen 2 en 3 van vorig antwoord naargelang k even of oneven is), maar dit werkt enkel voor de speciale gevallen waar n een kwadraat is. Of je voor deze bijzondere gevallen dan echt de kleinst mogelijke m-waarde hebt, zie ik niet direct in. Misschien bestaat er nog een andere splitsing die kleinere m toelaat. De grootste beperking vind ik echter dat het enkel voor kwadratische n werkt...

Je had het ook over m=1 (mod 4). Volgens mij is deze eis niet nodig en je overgang op x dus ook niet. Bovendien geldt je splitsing enkel voor die berekende m-waarde en helemaal niet voor grotere waarden (tenzij je in de kritische grens bereikt vanaf waar mijn splitsing werkt of tenzij er nog een andere splitsingsaanpak bestaat).
Bv.: {1,2}+{3}: n=1² en m=2.1+1 of {4,5,6}+{7,8}: n=2² en m=2.2+1

Er blijft dus nog wat speurderswerk over...

Groetjes,
Johan

andros
10-12-2003