info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Eine Menge. Übersichtlich. Nicht unendlich. Vertrackt ...
54 views
Skip to first unread message
Brigitta Jennen
Jul 24, 2022, 8:05:19 AM7/24/22
to
Hallo,
nachfolgend eine Aufgabe, über die ich gestolpert bin:
Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
Aufgabe:
(1) eliminiere eine Zahl k aus diesen 10 Zahlen
(2) teile die verbleibenden Zahlen in zwei Gruppen A und B
(3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
(4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
Jetzt bestimme k so, dass
die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
Eine Lösung habe ich unten nach dem Spoiler angegeben.
Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
beweisen? Geht das irgendwie analytisch?
Und zum Weiterknobeln:
(a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
(b) Gibt es für ein anderes n < 10 ebenfalls eine Lösung? Welche?
(c) Gibt es Lösungen für n > 10, wenn man zwei Zahlen (k1, k2),
drei Zahlen (k1, k2, k3), … eliminiert?
Viel Spass und Grüße Brigitta
<Spoiler>
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
------------------------------------------------------------
Lösung für n=10:
mit k = 7 ergibt sich
Gruppe A = {1, 3, 4, 6, 10}. mit Summe = 24, Produkt = 720
Gruppe B = {2, 5, 8, 9} ebf. mit Summe = 24, Produkt = 720
</Spoiler>
nachfolgend eine Aufgabe, über die ich gestolpert bin:
Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
Aufgabe:
(1) eliminiere eine Zahl k aus diesen 10 Zahlen
(2) teile die verbleibenden Zahlen in zwei Gruppen A und B
(3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
(4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
Jetzt bestimme k so, dass
die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
Eine Lösung habe ich unten nach dem Spoiler angegeben.
Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
beweisen? Geht das irgendwie analytisch?
Und zum Weiterknobeln:
(a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
(b) Gibt es für ein anderes n < 10 ebenfalls eine Lösung? Welche?
(c) Gibt es Lösungen für n > 10, wenn man zwei Zahlen (k1, k2),
drei Zahlen (k1, k2, k3), … eliminiert?
Viel Spass und Grüße Brigitta
<Spoiler>
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
------------------------------------------------------------
Lösung für n=10:
mit k = 7 ergibt sich
Gruppe A = {1, 3, 4, 6, 10}. mit Summe = 24, Produkt = 720
Gruppe B = {2, 5, 8, 9} ebf. mit Summe = 24, Produkt = 720
</Spoiler>
Stefan Schmitz
Jul 24, 2022, 8:59:43 AM7/24/22
to
Am 24.07.2022 um 14:05 schrieb Brigitta Jennen:
> Hallo,
> nachfolgend eine Aufgabe, über die ich gestolpert bin:
>
> Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
> M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
>
> Aufgabe:
>
> (1) eliminiere eine Zahl k aus diesen 10 Zahlen
> (2) teile die verbleibenden Zahlen in zwei Gruppen A und B
> (3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
> (4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
>
> Jetzt bestimme k so, dass
> die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
> Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
> Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
>
> Eine Lösung habe ich unten nach dem Spoiler angegeben.
> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
> beweisen? Geht das irgendwie analytisch?
Zunächst mal muss die 7 die eliminierte Zahl sein, weil sonst ein
> Hallo,
> nachfolgend eine Aufgabe, über die ich gestolpert bin:
>
> Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
> M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
>
> Aufgabe:
>
> (1) eliminiere eine Zahl k aus diesen 10 Zahlen
> (2) teile die verbleibenden Zahlen in zwei Gruppen A und B
> (3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
> (4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
>
> Jetzt bestimme k so, dass
> die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
> Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
> Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
>
> Eine Lösung habe ich unten nach dem Spoiler angegeben.
> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
> beweisen? Geht das irgendwie analytisch?
Primfaktor in einer Gruppe fehlt.
Dann muss 9 in einer anderen Gruppe als 3 und 6 sein, damit beide den
Faktor 9 haben. Ebenso 8 und 4 sowie 10 und 5. Die verbleibenden
Möglichkeiten wird man dann ausprobieren müssen.
> Und zum Weiterknobeln:
> (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
Summe der Exponenten eines Primfaktors ungerade, muss also in den beiden
Gruppen verschieden sein. Entfernt man die 4, kann die 8 nicht
ausgeglichen werden. Und wenn die 1 fehlt, geht die Summe nicht mehr auf.
> (b) Gibt es für ein anderes n < 10 ebenfalls eine Lösung? Welche?
Für n=6 kann man in {1,3,4], {2,6} aufteilen.
Bei n<6 müsste die 4 gestrichen werden, dann ist das eine Produkt
gerade, das andere ungerade.
> (c) Gibt es Lösungen für n > 10, wenn man zwei Zahlen (k1, k2),
> drei Zahlen (k1, k2, k3), … eliminiert?
Ansonsten müssen für wachsendes n immer mehr Zahlen gestrichen werden,
weil Primfaktoren hinzukommen, die nur einmal auftauchen.
Carlos Naplos
Jul 25, 2022, 5:05:15 AM7/25/22
to
Am 24.07.2022 um 14:59 schrieb Stefan Schmitz:
> Zunächst mal muss die 7 die eliminierte Zahl sein, weil sonst ein
> Primfaktor in einer Gruppe fehlt.
> Dann muss 9 in einer anderen Gruppe als 3 und 6 sein, damit beide den
> Faktor 9 haben. Ebenso 8 und 4 sowie 10 und 5. Die verbleibenden
> Möglichkeiten wird man dann ausprobieren müssen.
Man kann folgendes überlegen:
> Zunächst mal muss die 7 die eliminierte Zahl sein, weil sonst ein
> Primfaktor in einer Gruppe fehlt.
> Dann muss 9 in einer anderen Gruppe als 3 und 6 sein, damit beide den
> Faktor 9 haben. Ebenso 8 und 4 sowie 10 und 5. Die verbleibenden
> Möglichkeiten wird man dann ausprobieren müssen.
Die Summe 1 + 2 + 3 + 4 + 5 + 6 + 8 + 9 + 10 ergibt 48, die der Gruppen
A und B also 24.
Sei o.B.d.A. 8 in der Gruppe A, also 4 in Gruppe B.
Dann kommt zu A mit entweder 3 und 6 oder 9 die Summe 9 hinzu.
Damit ist die Summe von A schon >= 17.
Dann muss 10 in Gruppe B und 5 in Gruppe A.
Damit ist die Summe von A schon >= 22.
Um auf 24 zu kommen, muss die 2 noch in Gruppe A, 1 in Gruppe B.
Offen ist noch, ob 3 und 6 oder 9 in Gruppe A können.
Da mit 2 und 8 aber schon die Hälfte der Faktoren 2 in A sind, muss 6
(und 3) nach B und 9 nach A.
Gruß CN
Brigitta Jennen
Jul 26, 2022, 7:26:07 AM7/26/22
to
Stefan Schmitz schrieb am Sonntag, 24. Juli 2022 um 14:59:43 UTC+2:
...
OK - belassen wir n= 10 und streichen jetzt zwei Zahlen.
Was ist, wenn ich
k1 = 4
k2 = 7
als zu streichende Zahlen nehme? Dann bleibt als
Restmenge übrig
{1, 2, 3, 5, 6, 8, 9, 10}
und ich kann die beiden Gruppen bilden
A = {1, 2, 3, 6, 10}
B = {5, 8, 9}
mit
SUM_A = 22, PROD_A = 360
SUM_B = 22, PROD_B = 360
Gruß B.
...
> > (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
> Nein. Wenn man eine weitere Zahl (außer 4 und 1) entfernt, wird die
> Summe der Exponenten eines Primfaktors ungerade, muss also in den beiden
> Gruppen verschieden sein. Entfernt man die 4, kann die 8 nicht
> ausgeglichen werden. Und wenn die 1 fehlt, geht die Summe nicht mehr auf.
Das hab ich nicht verstanden.
> Nein. Wenn man eine weitere Zahl (außer 4 und 1) entfernt, wird die
> Summe der Exponenten eines Primfaktors ungerade, muss also in den beiden
> Gruppen verschieden sein. Entfernt man die 4, kann die 8 nicht
> ausgeglichen werden. Und wenn die 1 fehlt, geht die Summe nicht mehr auf.
OK - belassen wir n= 10 und streichen jetzt zwei Zahlen.
Was ist, wenn ich
k1 = 4
k2 = 7
als zu streichende Zahlen nehme? Dann bleibt als
Restmenge übrig
{1, 2, 3, 5, 6, 8, 9, 10}
und ich kann die beiden Gruppen bilden
A = {1, 2, 3, 6, 10}
B = {5, 8, 9}
mit
SUM_A = 22, PROD_A = 360
SUM_B = 22, PROD_B = 360
Gruß B.
Stefan Schmitz
Jul 26, 2022, 9:34:40 AM7/26/22
to
Dass man den Faktor 8 auch mit 2,6,10 erreicht, hatte ich übersehen.
Carlo XYZ
Jul 26, 2022, 9:38:27 AM7/26/22
to
Brigitta Jennen schrieb am 26.07.22 um 13:26:
> Was ist, wenn ich
> k1 = 4
> k2 = 7
> als zu streichende Zahlen nehme? Dann bleibt als
> Restmenge übrig
>
> {1, 2, 3, 5, 6, 8, 9, 10}
>
> und ich kann die beiden Gruppen bilden
>
> A = {1, 2, 3, 6, 10}
> B = {5, 8, 9}
>
> mit
>
> SUM_A = 22, PROD_A = 360
> SUM_B = 22, PROD_B = 360
Also wenn du so eine Zahlenreihe hast, dann kannst du
schon mal genau ausrechnen, wie groß die Summe und wie
groß das Produkt sein müssen:
Für die Summe addiere alle Zahlen (gibt hier 44)
und dividiere durch 2 (ergibt 22).
Für das Produkt multipliziere alle Zahlen (macht
hier 129600) und ziehe die Quadratwurzel (also 360).
Das gibt dir immerhin schon mal zwei Kriterien, wann es
_nicht_ geht: wenn die Summe nicht durch 2 teilbar ist,
bzw. wenn das Produkt keine Quadratzahl ist. Das heißt
aber nicht, dass es immer geht, wenn die Summe gerade
und das Produkt eine Quadratzahl ist.
Außerdem hast du das Problem auf die bekannten Probleme
"subset sum", kombiniert mit "subset product" reduziert.
Für die Kombination beider Probleme habe ich einige
Stellen gefunden, zum Beispiel:
<https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems>
und Stellen, die das eine auf das andere reduzieren.
Sehr ergiebig ist das nicht, aber immerhin scheint
das kombinierte Problem weiterhin NP-hart zu sein.
Das bedeutet insbesondere, dass es keine "leicht
zu sehende" Lösung gibt. Vielleicht kannst du für
den speziellen Fall von Zahlen zwischen 1 und 10
damit etwas anfangen.
> Was ist, wenn ich
> k1 = 4
> k2 = 7
> als zu streichende Zahlen nehme? Dann bleibt als
> Restmenge übrig
>
> {1, 2, 3, 5, 6, 8, 9, 10}
>
> und ich kann die beiden Gruppen bilden
>
> A = {1, 2, 3, 6, 10}
> B = {5, 8, 9}
>
> mit
>
> SUM_A = 22, PROD_A = 360
> SUM_B = 22, PROD_B = 360
schon mal genau ausrechnen, wie groß die Summe und wie
groß das Produkt sein müssen:
Für die Summe addiere alle Zahlen (gibt hier 44)
und dividiere durch 2 (ergibt 22).
Für das Produkt multipliziere alle Zahlen (macht
hier 129600) und ziehe die Quadratwurzel (also 360).
Das gibt dir immerhin schon mal zwei Kriterien, wann es
_nicht_ geht: wenn die Summe nicht durch 2 teilbar ist,
bzw. wenn das Produkt keine Quadratzahl ist. Das heißt
aber nicht, dass es immer geht, wenn die Summe gerade
und das Produkt eine Quadratzahl ist.
Außerdem hast du das Problem auf die bekannten Probleme
"subset sum", kombiniert mit "subset product" reduziert.
Für die Kombination beider Probleme habe ich einige
Stellen gefunden, zum Beispiel:
<https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems>
und Stellen, die das eine auf das andere reduzieren.
Sehr ergiebig ist das nicht, aber immerhin scheint
das kombinierte Problem weiterhin NP-hart zu sein.
Das bedeutet insbesondere, dass es keine "leicht
zu sehende" Lösung gibt. Vielleicht kannst du für
den speziellen Fall von Zahlen zwischen 1 und 10
damit etwas anfangen.
Stephan Gerlach
Jul 29, 2022, 7:15:10 PM7/29/22
to
Brigitta Jennen schrieb:
gilt, was ungerade ist, muß k ungerade sein. Mögliche Werte für SUM_A
bzw. SUM_B sind 23, 24, 25, 26, 27.
Problem ist, daß sich die Summen jeweils unterschiedlich realisieren
lassen, z.B.:
SUM_A = 2+4+6+7+8 = 27
SUM_B = 3+5+9+10 = 27.
Es geht aber auch
SUM_A = 2+3+4+8+10 = 27
SUM_B = 5+6+7+9 = 27.
> Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
Das Produkt aller 10 Zahlen ist
Produkt_{k∈M} k = 10!
Hier hilft u.U. eine Primfaktorzerlegung weiter:
10! = 2^8 * 3^4 * 5^2 * 7
Die 7 kommt als einziger Primfaktor in einer ungeraden Anzahl vor. Würde
man die 7 *nicht* weglassen, dann hätte eines der beiden Produkte PROD_A
oder PROD_B den Primfaktor 7, der andere aber nicht.
Also *muß* die 7 weggelassen werden.
Praktischerweise ist 7 ungerade, was zur "Summen-Bedingung" paßt, also:
k = 7.
> Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
Die beiden Bedingungen für A und B sind:
SUM_A = SUM_B = ((Summe_{k∈M} k) - 7)/2 = (55-7)/2 = 48/2 = 24,
PROD_A = PROD_B = sqrt(2^8 * 3^4 * 5^2) = 2^4 * 3^2 * 5.
Hätte man nur die Summen-Bedingung, gäbe es mehrere Lösungen.
Die Produkt-Bedingung führt auch hier schneller zum Ziel:
Eines der beiden Produkte (bzw. eine der beiden Mengen) muß die Zahl 5
enthalten; sei dies o.B.d.A. die Menge A. Dann enthält B wegen des
Primfaktors 5 die Zahl 10. Wir protokollieren mal den "Zusammenbau" der
Mengen A und B. Zu Beginn stehen für beide Mengen die Primfaktoren
2, 2, 2, 2, 3, 3, 5 zur "Verfügung":
A = {5; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 2, 3, 3
B = {10; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 3, 3
Jetzt betrachten wir die Primfaktoren 3: In einer der beiden Mengen muß
die Zahl 9 sein; folglich muß die andere Menge die Zahlen 3 und 6
enthalten. Ich sehe hier nicht, welche der genannten Zahlen in A und
welche in B gehören müssen; daher gibt es hier die folgenden Möglichkeiten:
A = {5; 9; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 2
B = {10; 3; 6; weitere Zahlen}
"übrige" Primfaktoren: 2, 2
oder aber
A = {5; 3; 6; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2
B = {10; 9; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2.
Jetzt müssen noch die übrigen Primfaktoren 2 auf die Zahlen 2, 4, 8
"verteilt" werden, mögliche Lösungen (ohne übrige Primfaktoren) für A
und B sind:
A = {5; 9; 2; 8}
B = {10; 3; 6; 4}
oder
A = {5; 3; 6; 2; 4}
B = {10; 9; 8}
oder
A = {5; 3; 6; 8}
B = {10; 9; 2; 4}.
Es bleibt noch die Zahl 1 "einzusortieren". Guckt man sich jetzt die
Summen-Bedingung an, sieht man schnell, daß nur die erste Lösung
überhaupt infrage kommt, da bei den anderen beiden Varianten die Summe
24 bei A und B jeweils nicht zustandekommt.
Da 5+9+2+8=24 ist, muß die 1 (bei der ersten Lösung) zu B einsortiert
werden; Lösung:
A = {5; 9; 2; 8}
B = {10; 3; 6; 4; 1}
Evtl. wäre es doch einfacher gewesen, nach dem Erkennen von k=7 die
Summen-Bedingung zu betrachten.
> Eine Lösung habe ich unten nach dem Spoiler angegeben.
Guck' ich mir gleich an.
> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
> beweisen? Geht das irgendwie analytisch?
Durch Ausschluß-Verfahren, wie ich es versucht habe, zu erklären. Ich
würde das nicht analytisch, sondern systematisch nennen. Wie gesagt ist
der wichtigste Schritt wohl, zu erkennen, daß k=7 ist. Danach ist es
wohl mehr ein Ausschluß-Verfahren. Zunächst gibt es ja (scheinbar)
mehrere Lösungen. Man muß eben gucken, daß nur beide Bedingungen
zusammen zu einer *eindeutigen* Lösung führen.
Evtl. gucken, welche Bedingung (Summen- oder Produkt-Bedingung)
praktischer zu handhaben ist.
> Und zum Weiterknobeln:
> (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
Da bin ich gerade zu faul dafür; auf jeden Fall muß wieder k1=7 sein,
und die andere Zahl k2 müßte 1, 4 oder 9 sein (wegen Primfaktorzerlegung).
> (b) Gibt es für ein anderes n < 10 ebenfalls eine Lösung? Welche?
> (c) Gibt es Lösungen für n > 10, wenn man zwei Zahlen (k1, k2),
> drei Zahlen (k1, k2, k3), … eliminiert?
Da bin ich jetzt zu faul dafür. Evtl. gibt es eine effizientere Methode
als meine oben, um die derart verallgemeinerte Aufgabe zu lösen.
> Viel Spass und Grüße Brigitta
>
> <Spoiler>
Hab' ich (ebenso wie die anderen Antworten) nicht gelesen, mach' ich
jetzt erst.
...
Entspricht genau meiner Lösung.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
> Hallo,
> nachfolgend eine Aufgabe, über die ich gestolpert bin:
>
> Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
> M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
>
> Aufgabe:
>
> (1) eliminiere eine Zahl k aus diesen 10 Zahlen
> (2) teile die verbleibenden Zahlen in zwei Gruppen A und B
> (3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
> (4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
>
> Jetzt bestimme k so, dass
> die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
Da
Summe_{k∈M} k = 55
> nachfolgend eine Aufgabe, über die ich gestolpert bin:
>
> Gegeben sei die Teilmenge der natürlichen Zahlen von 1 bis 10.
> M = {1, 2, 3, 4, 5, 6, 7, 8, 9 10}
>
> Aufgabe:
>
> (1) eliminiere eine Zahl k aus diesen 10 Zahlen
> (2) teile die verbleibenden Zahlen in zwei Gruppen A und B
> (3) bestimme die Summe der Zahlen in Gruppe A und Gruppe B
> (4) bestimme das Produkt der Zahlen in Gruppe A und Gruppe B
>
> Jetzt bestimme k so, dass
> die Summen in jeder Gruppe übereinstimmen: SUM_A = SUM_B.
Da
gilt, was ungerade ist, muß k ungerade sein. Mögliche Werte für SUM_A
bzw. SUM_B sind 23, 24, 25, 26, 27.
Problem ist, daß sich die Summen jeweils unterschiedlich realisieren
lassen, z.B.:
SUM_A = 2+4+6+7+8 = 27
SUM_B = 3+5+9+10 = 27.
Es geht aber auch
SUM_A = 2+3+4+8+10 = 27
SUM_B = 5+6+7+9 = 27.
> Das gleiche soll auch für die Produkte gelten: PROD_A = PROD_B.
Produkt_{k∈M} k = 10!
Hier hilft u.U. eine Primfaktorzerlegung weiter:
10! = 2^8 * 3^4 * 5^2 * 7
Die 7 kommt als einziger Primfaktor in einer ungeraden Anzahl vor. Würde
man die 7 *nicht* weglassen, dann hätte eines der beiden Produkte PROD_A
oder PROD_B den Primfaktor 7, der andere aber nicht.
Also *muß* die 7 weggelassen werden.
Praktischerweise ist 7 ungerade, was zur "Summen-Bedingung" paßt, also:
k = 7.
> Welche Zahlen sind in der Gruppe A, welche in der Gruppe B?
SUM_A = SUM_B = ((Summe_{k∈M} k) - 7)/2 = (55-7)/2 = 48/2 = 24,
PROD_A = PROD_B = sqrt(2^8 * 3^4 * 5^2) = 2^4 * 3^2 * 5.
Hätte man nur die Summen-Bedingung, gäbe es mehrere Lösungen.
Die Produkt-Bedingung führt auch hier schneller zum Ziel:
Eines der beiden Produkte (bzw. eine der beiden Mengen) muß die Zahl 5
enthalten; sei dies o.B.d.A. die Menge A. Dann enthält B wegen des
Primfaktors 5 die Zahl 10. Wir protokollieren mal den "Zusammenbau" der
Mengen A und B. Zu Beginn stehen für beide Mengen die Primfaktoren
2, 2, 2, 2, 3, 3, 5 zur "Verfügung":
A = {5; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 2, 3, 3
B = {10; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 3, 3
Jetzt betrachten wir die Primfaktoren 3: In einer der beiden Mengen muß
die Zahl 9 sein; folglich muß die andere Menge die Zahlen 3 und 6
enthalten. Ich sehe hier nicht, welche der genannten Zahlen in A und
welche in B gehören müssen; daher gibt es hier die folgenden Möglichkeiten:
A = {5; 9; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2, 2
B = {10; 3; 6; weitere Zahlen}
"übrige" Primfaktoren: 2, 2
oder aber
A = {5; 3; 6; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2
B = {10; 9; weitere Zahlen}
"übrige" Primfaktoren: 2, 2, 2.
Jetzt müssen noch die übrigen Primfaktoren 2 auf die Zahlen 2, 4, 8
"verteilt" werden, mögliche Lösungen (ohne übrige Primfaktoren) für A
und B sind:
A = {5; 9; 2; 8}
B = {10; 3; 6; 4}
oder
A = {5; 3; 6; 2; 4}
B = {10; 9; 8}
oder
A = {5; 3; 6; 8}
B = {10; 9; 2; 4}.
Es bleibt noch die Zahl 1 "einzusortieren". Guckt man sich jetzt die
Summen-Bedingung an, sieht man schnell, daß nur die erste Lösung
überhaupt infrage kommt, da bei den anderen beiden Varianten die Summe
24 bei A und B jeweils nicht zustandekommt.
Da 5+9+2+8=24 ist, muß die 1 (bei der ersten Lösung) zu B einsortiert
werden; Lösung:
A = {5; 9; 2; 8}
B = {10; 3; 6; 4; 1}
Evtl. wäre es doch einfacher gewesen, nach dem Erkennen von k=7 die
Summen-Bedingung zu betrachten.
> Eine Lösung habe ich unten nach dem Spoiler angegeben.
> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
> beweisen? Geht das irgendwie analytisch?
würde das nicht analytisch, sondern systematisch nennen. Wie gesagt ist
der wichtigste Schritt wohl, zu erkennen, daß k=7 ist. Danach ist es
wohl mehr ein Ausschluß-Verfahren. Zunächst gibt es ja (scheinbar)
mehrere Lösungen. Man muß eben gucken, daß nur beide Bedingungen
zusammen zu einer *eindeutigen* Lösung führen.
Evtl. gucken, welche Bedingung (Summen- oder Produkt-Bedingung)
praktischer zu handhaben ist.
> Und zum Weiterknobeln:
> (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2 eliminiert?
und die andere Zahl k2 müßte 1, 4 oder 9 sein (wegen Primfaktorzerlegung).
> (b) Gibt es für ein anderes n < 10 ebenfalls eine Lösung? Welche?
> (c) Gibt es Lösungen für n > 10, wenn man zwei Zahlen (k1, k2),
> drei Zahlen (k1, k2, k3), … eliminiert?
als meine oben, um die derart verallgemeinerte Aufgabe zu lösen.
> Viel Spass und Grüße Brigitta
>
> <Spoiler>
jetzt erst.
...
Entspricht genau meiner Lösung.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Carlo XYZ
Jul 30, 2022, 1:06:49 PM7/30/22
to
Stephan Gerlach schrieb am 30.07.22 um 01:33:
> Brigitta Jennen schrieb:
...
> Hier hilft u.U. eine Primfaktorzerlegung weiter:
> 10! = 2^8 * 3^4 * 5^2 * 7
Ja.
> Die 7 kommt als einziger Primfaktor in einer ungeraden Anzahl vor. Würde
> man die 7 *nicht* weglassen, dann hätte eines der beiden Produkte PROD_A
> oder PROD_B den Primfaktor 7, der andere aber nicht.
> Also *muß* die 7 weggelassen werden.
>
> Praktischerweise ist 7 ungerade, was zur "Summen-Bedingung" paßt, also:
> k = 7.
Das heißt aber noch lange nicht, dass es dann geht. (Hier schon.)
>> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
>> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
>> beweisen? Geht das irgendwie analytisch?
>
> Durch Ausschluß-Verfahren, wie ich es versucht habe, zu erklären.
Also systematisches Ausprobieren, und das geht i.W. z.Zt. auch
nicht anders, weil das Problem subset sum bereits NP-hart ist.
Hier geht's auch noch etwas anders als von dir aufgeschrieben
(aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
9 kann nicht in B, sonst wird die Summe zu groß
(kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
Wegen Primfaktor 3 müssen 6 und 3 in B.
8 muss in A, sonst wird das Produkt bei B zu groß.
Danach ist klar, wie 1,2,4 verteilt werden.
> Man muß eben gucken, daß nur beide Bedingungen zusammen zu einer *eindeutigen* Lösung führen.
Allerdings kann es i.A. mehr als nur eine Lösung geben.
>> Und zum Weiterknobeln:
>> (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2
>> eliminiert?
>
> Da bin ich gerade zu faul dafür; auf jeden Fall muß wieder k1=7 sein,
> und die andere Zahl k2 müßte 1, 4 oder 9 sein (wegen Primfaktorzerlegung).
1 und 9 geht beides nicht, wegen Geradheit von 1+7 und 9+7. Also 4.
> Brigitta Jennen schrieb:
...
> Hier hilft u.U. eine Primfaktorzerlegung weiter:
> 10! = 2^8 * 3^4 * 5^2 * 7
> Die 7 kommt als einziger Primfaktor in einer ungeraden Anzahl vor. Würde
> man die 7 *nicht* weglassen, dann hätte eines der beiden Produkte PROD_A
> oder PROD_B den Primfaktor 7, der andere aber nicht.
> Also *muß* die 7 weggelassen werden.
>
> Praktischerweise ist 7 ungerade, was zur "Summen-Bedingung" paßt, also:
> k = 7.
>> Was mich aber viel mehr interessiert: Wenn das die einzig (mögliche)
>> Lösung bei n=10 Zahlen ist, wie kann ich das ohne explizites Aufschreiben
>> beweisen? Geht das irgendwie analytisch?
>
> Durch Ausschluß-Verfahren, wie ich es versucht habe, zu erklären.
nicht anders, weil das Problem subset sum bereits NP-hart ist.
Hier geht's auch noch etwas anders als von dir aufgeschrieben
(aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
9 kann nicht in B, sonst wird die Summe zu groß
(kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
Wegen Primfaktor 3 müssen 6 und 3 in B.
8 muss in A, sonst wird das Produkt bei B zu groß.
Danach ist klar, wie 1,2,4 verteilt werden.
> Man muß eben gucken, daß nur beide Bedingungen zusammen zu einer *eindeutigen* Lösung führen.
>> Und zum Weiterknobeln:
>> (a) Gibt es eine Lösung (bei gleichem n), wenn man zwei Zahlen k1, k2
>> eliminiert?
>
> Da bin ich gerade zu faul dafür; auf jeden Fall muß wieder k1=7 sein,
> und die andere Zahl k2 müßte 1, 4 oder 9 sein (wegen Primfaktorzerlegung).
Stefan Schmitz
Jul 31, 2022, 5:54:52 AM7/31/22
to
Am 30.07.2022 um 19:06 schrieb Carlo XYZ:
> Hier geht's auch noch etwas anders als von dir aufgeschrieben
> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>
> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>
> 9 kann nicht in B, sonst wird die Summe zu groß
> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>
> Wegen Primfaktor 3 müssen 6 und 3 in B.
Das Argument mit der zu hohen Summe kann ich an dieser Stelle nicht
> Hier geht's auch noch etwas anders als von dir aufgeschrieben
> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>
> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>
> 9 kann nicht in B, sonst wird die Summe zu groß
> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>
> Wegen Primfaktor 3 müssen 6 und 3 in B.
nachvollziehen.
19 ist noch deutlich unter der angestrebten Summe, und außerdem trägt
die 9 nicht mehr dazu bei als 3 und 6
Carlo XYZ
Jul 31, 2022, 6:42:24 AM7/31/22
to
Stefan Schmitz schrieb am 31.07.22 um 11:54:
Nicht viel, nur 5. Das geht nur, wie ich schrieb,
mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
> und außerdem trägt die 9 nicht mehr dazu bei als 3 und 6
Wir überlegen uns hier, wo die 9 hinkommt,
und nicht, wo die 6 oder 3 hinkommen.
Heuristik: Verteile zuerst Zahlen, die 1) Primfaktoren
kleiner Vielfachheit haben, 2) möglichst groß sind. Am
besten beides. Hier passt die 10 super als erste Zahl.
mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
> und außerdem trägt die 9 nicht mehr dazu bei als 3 und 6
und nicht, wo die 6 oder 3 hinkommen.
Heuristik: Verteile zuerst Zahlen, die 1) Primfaktoren
kleiner Vielfachheit haben, 2) möglichst groß sind. Am
besten beides. Hier passt die 10 super als erste Zahl.
Stefan Schmitz
Jul 31, 2022, 8:57:39 AM7/31/22
to
Am 31.07.2022 um 12:42 schrieb Carlo XYZ:
> Stefan Schmitz schrieb am 31.07.22 um 11:54:
>
>> Am 30.07.2022 um 19:06 schrieb Carlo XYZ:
>>
>>> Hier geht's auch noch etwas anders als von dir aufgeschrieben
>>> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>>>
>>> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>>>
>>> 9 kann nicht in B, sonst wird die Summe zu groß
>>> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>>>
>>> Wegen Primfaktor 3 müssen 6 und 3 in B.
>>
>> Das Argument mit der zu hohen Summe kann ich an dieser Stelle nicht
>> nachvollziehen.
>> 19 ist noch deutlich unter der angestrebten Summe,
>
> Nicht viel, nur 5. Das geht nur, wie ich schrieb,
> mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
Das wäre prinzipiell kein Problem. Führt nur deswegen zu keiner Lösung,
> Stefan Schmitz schrieb am 31.07.22 um 11:54:
>
>> Am 30.07.2022 um 19:06 schrieb Carlo XYZ:
>>
>>> Hier geht's auch noch etwas anders als von dir aufgeschrieben
>>> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>>>
>>> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>>>
>>> 9 kann nicht in B, sonst wird die Summe zu groß
>>> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>>>
>>> Wegen Primfaktor 3 müssen 6 und 3 in B.
>>
>> Das Argument mit der zu hohen Summe kann ich an dieser Stelle nicht
>> nachvollziehen.
>> 19 ist noch deutlich unter der angestrebten Summe,
>
> Nicht viel, nur 5. Das geht nur, wie ich schrieb,
> mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
weil dann einer der Primfaktoren 2 oder 3 zu selten vorkäme, was du aber
nicht erwähnt hast.
>> und außerdem trägt die 9 nicht mehr dazu bei als 3 und 6
>
> Wir überlegen uns hier, wo die 9 hinkommt,
> und nicht, wo die 6 oder 3 hinkommen.
> Heuristik: Verteile zuerst Zahlen, die 1) Primfaktoren
> kleiner Vielfachheit haben, 2) möglichst groß sind. Am
> besten beides. Hier passt die 10 super als erste Zahl.
auch als zweites die 9 genommen und nicht die 3.
Carlo XYZ
Jul 31, 2022, 10:45:02 AM7/31/22
to
Stefan Schmitz schrieb am 31.07.22 um 14:57:
> Am 31.07.2022 um 12:42 schrieb Carlo XYZ:
>> Stefan Schmitz schrieb am 31.07.22 um 11:54:
>>
>>> Am 30.07.2022 um 19:06 schrieb Carlo XYZ:
>>>
>>>> Hier geht's auch noch etwas anders als von dir aufgeschrieben
>>>> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>>>>
>>>> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>>>>
>>>> 9 kann nicht in B, sonst wird die Summe zu groß
>>>> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>>>>
>>>> Wegen Primfaktor 3 müssen 6 und 3 in B.
>>>
>>> Das Argument mit der zu hohen Summe kann ich an dieser Stelle nicht
>>> nachvollziehen.
>>> 19 ist noch deutlich unter der angestrebten Summe,
>>
>> Nicht viel, nur 5. Das geht nur, wie ich schrieb,
>> mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
>
> Das wäre prinzipiell kein Problem. Führt nur deswegen zu keiner Lösung,
> weil dann einer der Primfaktoren 2 oder 3 zu selten vorkäme, was du aber
> nicht erwähnt hast.
Verzeih, dass ich nicht alles klitzeklein vorgekaut habe.
Ich habe aber darauf hingewiesen, dass es etwas zu kauen
gibt und angenommen, dass du bzw. der Leser im Allgemeinen
Zähne im Kopf besitzt.
Ungewohnt könnte vielleicht sein, dass ich beides (subset
sum und subset product) abwechselnd benutze, je nachdem,
was gerade passt. Das ist von Vorteil - ich darf es aber.
>>> und außerdem trägt die 9 nicht mehr dazu bei als 3 und 6
>>
>> Wir überlegen uns hier, wo die 9 hinkommt,
>> und nicht, wo die 6 oder 3 hinkommen.
>
> Für das Argument "Summe zu hoch" ist das egal.
Dieser Fall entsteht gar nicht. Ich habe von der Heuristik
mit Priorität "größere Zahlen zuerst" verwendet und es ging.
Du darfst es gerne andersherum versuchen, vielleicht findest
du sogar einen kürzeren Lösungsweg. Einer genügt allerdings,
um die Eindeutigkeit zu beweisen.
>> Heuristik: Verteile zuerst Zahlen, die 1) Primfaktoren
>> kleiner Vielfachheit haben, 2) möglichst groß sind. Am
>> besten beides. Hier passt die 10 super als erste Zahl.
>
> Bei 1) würde ich ja zuerst die große Vielfachheit verteilen. Du hast ja
> auch als zweites die 9 genommen und nicht die 3.
Das habe ich als Erstes versucht, weil 9>3, und es hat funktioniert.
Ich glaube kaum, dass eine allgemeingültige Heuristik bekannt ist,
die immer schnellstmöglich zum Ziel führt. Meine habe ich auch nur
on-the-fly erfunden und nicht aus der Literatur. Ich behaupte nicht,
dass sie bestmöglich ist.
> Am 31.07.2022 um 12:42 schrieb Carlo XYZ:
>> Stefan Schmitz schrieb am 31.07.22 um 11:54:
>>
>>> Am 30.07.2022 um 19:06 schrieb Carlo XYZ:
>>>
>>>> Hier geht's auch noch etwas anders als von dir aufgeschrieben
>>>> (aber sicherlich irgendwie äquivalent). Wir bilden 2 Mengen A,B.
>>>>
>>>> 10 kommt in B, dann muss 5 in A wegen Primfaktor 5.
>>>>
>>>> 9 kann nicht in B, sonst wird die Summe zu groß
>>>> (kleine Nebenüberlegung, wieso nicht 2+3 oder 1+4), also 9 in A.
>>>>
>>>> Wegen Primfaktor 3 müssen 6 und 3 in B.
>>>
>>> Das Argument mit der zu hohen Summe kann ich an dieser Stelle nicht
>>> nachvollziehen.
>>> 19 ist noch deutlich unter der angestrebten Summe,
>>
>> Nicht viel, nur 5. Das geht nur, wie ich schrieb,
>> mit 2+3 oder 1+4, und ist die "kleine Nebenüberlegung".
>
> Das wäre prinzipiell kein Problem. Führt nur deswegen zu keiner Lösung,
> weil dann einer der Primfaktoren 2 oder 3 zu selten vorkäme, was du aber
> nicht erwähnt hast.
Ich habe aber darauf hingewiesen, dass es etwas zu kauen
gibt und angenommen, dass du bzw. der Leser im Allgemeinen
Zähne im Kopf besitzt.
Ungewohnt könnte vielleicht sein, dass ich beides (subset
sum und subset product) abwechselnd benutze, je nachdem,
was gerade passt. Das ist von Vorteil - ich darf es aber.
>>> und außerdem trägt die 9 nicht mehr dazu bei als 3 und 6
>>
>> Wir überlegen uns hier, wo die 9 hinkommt,
>> und nicht, wo die 6 oder 3 hinkommen.
>
> Für das Argument "Summe zu hoch" ist das egal.
mit Priorität "größere Zahlen zuerst" verwendet und es ging.
Du darfst es gerne andersherum versuchen, vielleicht findest
du sogar einen kürzeren Lösungsweg. Einer genügt allerdings,
um die Eindeutigkeit zu beweisen.
>> Heuristik: Verteile zuerst Zahlen, die 1) Primfaktoren
>> kleiner Vielfachheit haben, 2) möglichst groß sind. Am
>> besten beides. Hier passt die 10 super als erste Zahl.
>
> Bei 1) würde ich ja zuerst die große Vielfachheit verteilen. Du hast ja
> auch als zweites die 9 genommen und nicht die 3.
Ich glaube kaum, dass eine allgemeingültige Heuristik bekannt ist,
die immer schnellstmöglich zum Ziel führt. Meine habe ich auch nur
on-the-fly erfunden und nicht aus der Literatur. Ich behaupte nicht,
dass sie bestmöglich ist.
0 new messages