Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Partition von {1, 2, ..., 3n} mit bestimmten Eigenschaften
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Partition von {1, 2, ..., 3n} mit bestimmten Eigenschaften
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-04-09


Hallo zusammen,

wäre toll, wenn mir jemand weiterhelfen könnte.

Es sei \(n>0\),
\[\bigcup_{i=1}^n\{a_{i,1},a_{i,2},a_{i,3}\}=\{1,2,...,3n\}\] eine Partition, und es gelte \(a_{i,1}+a_{i,2}=a_{i,3}\) für \(i=1,...,n\). Weiter sei \(a_{1,1}<a_{2,1}<...<a_{n,1}\). [Nachtrag: Diese letzte Voraussetzung ist vermutlich sogar überflüssig.]

Aus der Menge \(\{1,2,...,3n\}\) werden nun die ersten \(k\) Mengen \(\{a_{i,1},a_{i,2},a_{i,3}\}\) entfernt; übrig bleiben \(3n-3k\) Elemente:
\[\{b_1,b_2,...,b_{3n-3k}\}=\{1,2,...,3n\}\setminus\bigcup_{i=1}^k\{a_{i,1},a_{i,2},a_{i,3}\}\] Es gelte \(b_1<b_2<...<b_{3n-3k}\).

Die Behauptung lautet nun, dass dann die Summe \(S_1\) der ersten zweidrittel der \(b_i\)'s kleiner oder gleich der Summe \(S_2\) des letzten Drittels der \(b_i\)'s ist, also
\[S_1:=\sum_{i=1}^{2n-2k}b_i \stackrel!\leq S_2:=\sum_{i=2n-2k+1}^{3n-3k}b_i\]
Ein Beispiel für \(n=13,k=6\)
Partition von {1, 2, ..., 39}:
(1 36 37) (2 10 12) (3 29 32) (4 21 25) (5 33 38) (6 24 30) (7 19 26)
(8 27 35) (9 14 23) (11 20 31) (13 15 28) (16 18 34) (17 22 39)
 
b1 ... b14: 7 8 9 11 13 14 15 16 17 18 19 20 22 23
b15 ... b21: 26 27 28 31 34 35 39
 
S1 = 212, S2 = 220 - Behauptung stimmt!

Ich dachte erst, die Sache wäre klar, aber ich bekomme den Beweis nicht hin.

Für \(n\leq13\) stimmt die Behauptung anscheinend. (Habe alle Möglichkeiten durchprobiert - hoffentlich.) Für \(n=14\) oder \(n=15\) stimmt die Behauptung, da es keine derartige Partition von \(\{1,2,...,3n\}\) gibt, wie man sich leicht überlegt.

Für mich interessant ist der Fall \(n=16\). Hier alle Möglichkeiten durchzuprobieren übersteigt meine Rechnerleistung.

Danke fürs Nachdenken und viele Grüße
StrgAltEntf



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 497
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-09


Hey,

also ich würde eine Rückwärtsinduktion über k vorschlagen. Für k=n oder k=n-1 ist die Aussage wahr.

Im Induktionsschritt von $k+1$ auf $k$ sei die Notation wie in deinem Post. Wir finden $b_i<b_j<b_o$ mit $b_i+b_j=b_o$, sodass $\{i,j,o\}\not\subseteq \{1,\ldots 2n-2k\}$ oder in Prosa: Nicht alle drei $b$'s sollen auf der linken Seite der Ungleichung auftauchen.

Nach Induktion ist die Aussage auch wahr, wenn wir zusammen mit den $a's$ auch noch diese drei $b$'s entfernen.
Durch die Eigenschaft $b_i+b_j=b_o$ ist dann die zu zeigende Ungleichung auch wahr. Dafür müsste man schnell die Fälle durchgehen..

Ist die Skizze verständlich (und richtig :D?)
Edit: Das ist doch gefährlicher als ich dachte, da sich die Anzahl der Summanden auf den beiden Seiten ändert im Induktionsschritt.. Als Ansatz lass ich es mal stehen..

Grüße
Creasy


-----------------
Smile (:



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6380
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-04-09


In dem Beispiel sind kleine Fehler. Die 26 gehört zu den "großen" Zahlen und die 23 zu den "kleinen", oder verstehe ich da etwas falsch? Außerdem ist die 38 nicht enthalten, dafür die 39.

Ist die Behauptung nicht offensichtlich?
Nimmt man alle $b_i$ und markiert dann jeweils die zwei "kleinen" Zahlen eines Tripel, so hat man in der Summe genau die Hälfte der Gesamtsumme markiert. Diese 2n-2k Zahlen sind zusammen mindestens so groß, wie die kleinsten 2n-2k Zahlen aus der Menge der $b_i$. Daraus folgt die Behauptung.

Im Beispiel:
Die 14 kleineren Zahlen der Tripel:
7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 27
Summe: 216
Die 7 jeweils größten Zahlen der Tripel:
23, 26, 28, 31, 34, 35, 39
Summe: 216

Die 14 kleinsten Zahlen insgesamt:
7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23
Summe: 212



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-04-10


2020-04-09 23:56 - Kitaktus in Beitrag No. 2 schreibt:
In dem Beispiel sind kleine Fehler. Die 26 gehört zu den "großen" Zahlen und die 23 zu den "kleinen", oder verstehe ich da etwas falsch? Außerdem ist die 38 nicht enthalten, dafür die 39.

Ist die Behauptung nicht offensichtlich?

Hallo Kitaktus,

das Beispiel habe ich korrigiert. Vielen Dank! Den Rest schaue ich mir morgen früh an; hoffe, es ist offensichtlich :-)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-04-10


Autsch!

Vielen Dank Kitaktus, und natürlich auch vielen Dank an Creasy!

Dass die Vermutung stimmt hatte ich im Gefühl, sonst hätte ich die Frage nicht gestellt. Erst hatte ich gedacht, es wäre einfach, zum Schluss hatte ich aber sogar dran gezweifelt. Schön, dass es nun doch so einfach ist!

Hier nochmal ein formaler Beweis. (Die Behauptung etwas einfacher formuliert.)

Es sei \(n>0\),
\[\bigcup_{i=1}^n\{a_{i,1},a_{i,2},a_{i,3}\}=\{1,2,...,3n\}\] eine Partition, und es gelte \(a_{i,1}+a_{i,2}=a_{i,3}\) für \(i=1,...,n\). [Die Voraussetzung \(a_{1,1}<a_{2,1}<...<a_{n,1}\) wird nicht benötigt.]

Weiter sei \(1\leq k\leq n\),
\[B:=\{b_1,b_2,...,b_{3k}\}=\bigcup_{i=1}^k\{a_{i,1},a_{i,2},a_{i,3}\}\] und es gelte \(b_1<b_2<...<b_{3k}\).

Behauptung:
\[S_1:=\sum_{i=1}^{2k}b_i \stackrel!\leq S_2:=\sum_{i=2k+1}^{3k}b_i\]
Beweis:
Setze \[M_1:=\bigcup_{i=1}^{k}\{a_{i,1},a_{i,2}\}, M_2:=\{a_{1,3},...,a_{k,3}\}\] Dann ist
\[S_1=\min_{M\subseteq B\wedge|M|=2k}\sum_{x\in M}x\leq \sum_{x\in M_1}x =  \sum_{x\in M_2}x\leq \max_{M\subseteq B\wedge|M|=k}\sum_{x\in M}x =S_2\] q. e. d.

Dann kann ich ja beruhigt mit meinem kleinen Projekt fortfahren. Später mehr dazu😃



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-04-11


Hallo,

ich habe mal eine Frage zur Definition Eurer "Partition".
Ich habe das mal mit mathematica programmiert und bekomme andere Teil-Gruppen:
mathematica
Partition von {1, 2, ..., 39}:
{{1, 29, 30}, {2, 7, 9}, {3, 28, 31}, {4, 6, 10}, {5, 27, 32}, {8, 25,
   33}, {11, 24, 35}, {12, 14, 26}, {13, 23, 36}, {15, 22, 37}, {16, 
  18, 34}, {17, 21, 38}, {19, 20, 39}}
 
u = Sort[Catenate[hinteren]]
 
b1 ... b14: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
b15 ... b21: 26, 34, 35, 36, 37, 38, 39
 
s1 = Sum[u[[i]], {i, 1, 2*n - 2*k}]
s2 = Sum[u[[i]], {i, 2*n - 2*k + 1, 3*n - 3*k}]
 245 <= 245
 
Behauptung stimmt!

Ich vermute, dass es durch die einfache Randbedingung mehrere gültige Partitionen gibt, die aber unabhängig von der zwischenzeitliche Teilgruppierung Deine gewünschte Behauptung immer erfüllen,
wie das ja im Beitrag 4 gezeigt wurde.
 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6380
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-04-11


Ja, in der Regel gibt es nicht nur eine Partition mit den geforderten Eigenschaften, wenn 3n(3n+1) durch 4 teilbar ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-04-11


2020-04-11 22:23 - hyperG in Beitrag No. 5 schreibt:
Ich vermute, dass es durch die einfache Randbedingung mehrere gültige Partitionen gibt, die aber unabhängig von der zwischenzeitliche Teilgruppierung Deine gewünschte Behauptung immer erfüllen,
wie das ja im Beitrag 4 gezeigt wurde.

Ja, es gibt sehr viele Partitionen. Um genau zu sein: 103372655. Und alle erfüllen die Behauptung. Ich hatte Zweifel, ob es eine Partition gibt, die die Behauptung nicht erfüllt. War das deine Frage?

[Die Antwort wurde nach Beitrag No.5 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-04-12


Konkret war meine Frage zur schwammigen Definition mit dem


\[\{b_1,b_2,...,b_{3n-3k}\}=\{1,2,...,3n\}\setminus\bigcup_{i=1}^k\{a_{i,1},a_{i,2},a_{i,3}\}\]
was einmal im Beitrag 1 als
n=13,k=6
Partition von {1, 2, ..., 39}:
(1 36 37) (2 10 12) (3 29 32) (4 21 25) (5 33 38) (6 24 30) (7 19 26)
(8 27 35) (9 14 23) (11 20 31) (13 15 28) (16 18 34) (17 22 39)
 
b1 ... b14: 7 8 9 11 13 14 15 16 17 18 19 20 22 23
b15 ... b21: 26 27 28 31 34 35 39
 
S1 = 212, S2 = 220 - Behauptung stimmt!

und von mir so interpretiert wurde:
mathematica n=13,k=6
Partition von {1, 2, ..., 39}:
{{1, 29, 30}, {2, 7, 9}, {3, 28, 31}, {4, 6, 10}, {5, 27, 32}, {8, 25,
   33}, {11, 24, 35}, {12, 14, 26}, {13, 23, 36}, {15, 22, 37}, {16, 
  18, 34}, {17, 21, 38}, {19, 20, 39}}
 
u = Sort[Catenate[hinteren]]
 
b1 ... b14: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
b15 ... b21: 26, 34, 35, 36, 37, 38, 39
 
s1 = Sum[u[[i]], {i, 1, 2*n - 2*k}]
s2 = Sum[u[[i]], {i, 2*n - 2*k + 1, 3*n - 3*k}]
 245 <= 245
 
Behauptung stimmt!

Oder anders: warum fängt Beitrag 1 mit dem Glied (1, 36, 37) an
wo doch schon {1, 29, 30} die Bedingung erfüllt?
Damit sieht doch das Array b & die beiden Summen komplett anders aus.

Ich weiß, dass es für den Beweis-Vergleich, der ja nur vom Typ Bool ist, unerheblich ist. Aber ich mag nun mal exakte Algorithmen, wo auch die Zwischenschritte übereinstimmen.

Zur Frage n=16 hat mein Algo auch noch keine einfache Partition mit allen Zahlen gefunden.

Für n=2 gibt es keine gültige Partition.

Fangen wir klein an:
"...wenn 3n(3n+1) durch 4 teilbar ist", wie sieht dann
Eure Partition für n=4 aus?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-04-12


Moin hyperG,

ich zerpflücke deinen Beitrag mal und antworte unten.

2020-04-12 00:51 - hyperG in Beitrag No. 8 schreibt:
1) Konkret war meine Frage zur schwammigen Definition mit dem

\[\{b_1,b_2,...,b_{3n-3k}\}=\{1,2,...,3n\}\setminus\bigcup_{i=1}^k\{a_{i,1},a_{i,2},a_{i,3}\}\]
2) was einmal im Beitrag 1 als [...] und von mir so interpretiert wurde: [...]

3) Oder anders: warum fängt Beitrag 1 mit dem Glied (1, 36, 37) an
wo doch schon {1, 29, 30} die Bedingung erfüllt?
Damit sieht doch das Array b & die beiden Summen komplett anders aus.

4) Aber ich mag nun mal exakte Algorithmen, wo auch die Zwischenschritte übereinstimmen.

5) Zur Frage n=16 hat mein Algo auch noch keine einfache Partition mit allen Zahlen gefunden.

6) Fangen wir klein an:
"...wenn 3n(3n+1) durch 4 teilbar ist", wie sieht dann
Eure Partition für n=4 aus?

1) Fandest du das schwammig? Die Zeile darunter (die du weggelassen hast) gehört sozusagen auch noch zur Definition der \(b_i\). Die Elemente der rechten Menge werden der Größe nach geordnet, und das Ergebnis ergibt \(b_1,b_2\) usw.

2) Das war doch nur ein Beispiel, das die Behauptung illustrieren soll. Ich hätte jede x-beliebige Partition nehmen können, die die Voraussetzungen erfüllt.

3) {1, 29, 30} ist doch genau so willkürlich. Man hätte auch eine Partition nehmen können, die mit {1, 2, 3} anfängt. Unterschiedliche Partitionen ergeben unterschiedliche \(b_i\)s und unterschiedliche Summen.

4) Ich auch. Der Input zum Algorithmus ist die Partition. Zwischenergebnisse sind die \(b_i\)s, \(S_1\) und \(S_2\). Output ist TRUE oder FALSE. Bei gleichem Input sollten immer die gleichen Zwischenergebnisse und der gleiche Output berechnet werden. Du hast aber einen anderen Input gewählt und kommst daher auf andere Zwischenergebnisse.

5) Ich habe mittlerweile ca. 50 Mrd.

6) Für n = 4 gibt es acht Partitionen. Eine ist {{1, 5, 6}, {2, 8, 10}, {3, 9, 12}, {4, 7, 11}}

Grüße und frohe Ostern
StrgAltEntf



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-04-12


Wenn bei gleichem Input n=13,k=6
bei Dir das Array
b[...]
{7 8 9 11 13 14 15 16 17 18 19 20 22 23 26 27 28 31 34 35 39}

und bei mir das Array
b[...]
{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 34, 35, 36, 37, 38, 39}

als Output herauskommt, ist das für mich für diesen Teil-Algorithmus nicht eindeutig. (vergleiche OEIS-Sequenzen)

Das nachträgliche Sortieren und so weiter soll erst mal nicht betrachtet werden.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-04-12


Noch einmal mit Hervorhebungen:

2020-04-12 10:46 - StrgAltEntf in Beitrag No. 9 schreibt:
4) Ich auch. Der Input zum Algorithmus ist die Partition. Zwischenergebnisse sind die \(b_i\)s, \(S_1\) und \(S_2\). Output ist TRUE oder FALSE. Bei gleichem Input sollten immer die gleichen Zwischenergebnisse und der gleiche Output berechnet werden. Du hast aber einen anderen Input gewählt und kommst daher auf andere Zwischenergebnisse.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-04-12


Noch ein Nachtrag. Vielleicht findet das jemand interessant oder aufschlussreich 😃

2020-04-12 10:46 - StrgAltEntf in Beitrag No. 9 schreibt:
6) Für n = 4 gibt es acht Partitionen. Eine ist {{1, 5, 6}, {2, 8, 10}, {3, 9, 12}, {4, 7, 11}}

Wieso gibt es eigentlich keine Partition von {1, 2, 3, ..., 12} (wie im TS bzw. Beitrag #4 beschrieben), die das Tripel {1, 2, 3}, {1, 3, 4} oder {1, 4, 5} enthält??

Tipp: Wende das in #4 Bewiesene an!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-04-13


Auch wenn nach 4) der Dich interessierende Algorithmus so aussieht:

f("Partition") as bool

finde ich den Teil-Algorithmus {mit einer einzigen eindeutigen "Zwischenergebnis-Partition"}

f(k,n) as {S1,S2}

schon deshalb interessanter, weil man damit eine schöne eindeutige &  übersichtliche Tabelle als Ergebnis bekommt:
Ergebnistabelle {S1,S2}
n\| k = 1      |      k=6
--+------------+------------
4 |33  <= 33   |
5 |52  <= 54   |
8 |119 <= 143  |
9 |182 <= 188  |
12|317 <= 341  |
13|324 <= 396  | 245 <= 245
..|...         |
28|1539 < 1907 | 1471 < 1605
29|1652 < 2046 | 1589 < 1729 
32|2015 < 2495 |
..|            |
48|4559 < 5665 |

(aus Zeitgründen noch nicht alle Felder gefüllt)

Beide S-Sequenzen für k=1 nicht in OEIS enthalten.

Als Regression ergibt S1(k=1,n) ~ (1.055311321*n + 2.490454615)^2.121911528 - 25.15131638

Etwas positives hat's auch gebracht: Mathematica besser kennengelernt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf hat die Antworten auf ihre/seine Frage gesehen.
StrgAltEntf hatte hier bereits selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]