Die Mathe-Redaktion - 23.09.2019 10:02 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 438 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » *(*) Gleichmäßige Potenzsummenpartition
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule *(*) Gleichmäßige Potenzsummenpartition
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-08-31


Anmerkung: Im Folgenden sei $0^0:=1$.

0) Kann man die Menge $W=\{0,1,2,\ldots,15\}$ in zwei disjunkte Mengen $A$ und $B$ mit $A\cup B=W$ zerlegen, so dass für alle $m\in\{0,1,2,3\}$ die Gleichung
\[
\sum_{a\in A}a^m=\sum_{b\in B}b^m
\] gilt?

a) Kann man die Menge $X=\{0,1,2,3,\ldots, 25,26\}$ in drei paarweise disjunkte Teilmengen $A,B,C$ mit $A\cup B\cup C=X$ zerlegen, so dass für alle $m\in\{0,1,2\}$ die Gleichung
\[\sum_{k\in A}k^m=\sum_{k\in B}k^m=\sum_{k\in C}k^m\] gilt?


b) Kann man die Menge $Y=\{k\in \IN\mid k< 2018^{2018}\}=\{0,1,2,3,\ldots, 2018^{2018}-1\}$ in 2018 paarweise disjunkte Teilmengen $A_1,A_2,\ldots, A_{2018}$  mit $A_1\cup A_2\cup \ldots \cup A_{2018}=Y$ zerlegen, so dass für jedes $m\in \IN, 0\leq m<2018$ und alle $1\leq i,j\leq 2018$ die Gleichung
\[\sum_{k\in A_i}k^m =\sum_{k\in A_j}k^m \] gilt?

Tipp:

Was hat eine schwedische Popgruppe mit dieser Aufgabe zu tun?

Nächster Tipp:





  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2018-09-01


Ich habe noch einen etwas handlicheren ersten Teil hinzugefügt.



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 1049
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-09-01


Zu a)
Es müssen nicht alle 27 Zahlen in den 3 Mengen untergebracht werden, sondern jeweils nur 3?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-09-01


Doch, es müssen alle 27 Zahlen untergebracht werden. Es soll also $A\cup B\cup C=\{0,1,\ldots, 26\}$ gelten. Das meinte ich mit dem Wort "zerlegen".



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 1049
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-09-01


Okay, dann hatte ich b) am Anfang schon falsch verstanden :D



  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-09-01


Zu a: \(0^0\) ist doch undefiniert, soll das hier jetzt einfach 1 sein? Also bei \(m=0\) steht dann ja in irgendeiner Summe dieser Ausdruck.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-09-01


@np_complete: Ja, für diese Aufgabe soll der Ausdruck $0^0$ gleich 1 sein.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2018-09-22


*push*

Da noch keine Lösungen abgegeben wurden, habe ich mich entschlossen jetzt doch noch die Aufgabe in der Version zu stellen, in der ich sie im Internet gefunden habe:

0) Kann man die Menge $W=\{0,1,2,\ldots,15\}$ in zwei disjunkte Mengen $A$ und $B$ mit $A\cup B=W$ zerlegen, so dass für alle $m\in\{0,1,2,3\}$ die Gleichung
\[
\sum_{a\in A}a^m=\sum_{b\in B}b^m
\] gilt?

Tipp:

Was hat eine schwedische Popgruppe mit dieser Aufgabe zu tun?






  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-09-23


Die ersten Lösungen für 0) und a) kamen von tactac. Herzlichen Glückwunsch!



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-09-23


Auch ochen hat eine Lösung für 0) gefunden. Glückwunsch!



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2018-09-29


Nächster Tipp:



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-10-01


Die Goldmedaille für die erste vollständige Lösung aller drei Teile geht an digerdiga. Super Leistung!



  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1351
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-10-01


Ist die Aufgabe eigentlich mit einem großen PC in absehbarer Zeit auch per brute force zu lösen? Nicht dass man sich die Lösung anschauen könnte, aber der PC kann dann ja sagen "hab was"^^



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2018-10-02


0) und a) kann man mit brute force lösen (tactac hat es so gemacht). Bei b) würde ich mal zu nein tendieren, da schon untere Schranken für die Anzahl der Kandidaten für $A_1$ deutlich größer sind als die Anzahl der Atome im beobachtbaren Universum.



  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1351
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-10-02



...da schon untere Schranken für die Anzahl der Kandidaten für A1 deutlich größer sind als die Anzahl der Atome im beobachtbaren Universum.
Da ist was dran...

Du sagtest du hättest die Aufgabe woanders im Netz gefunden? Stand da auch eine allgemeine "Musterlösung" bzw. hattest du bereits eine?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2018-10-02


Ich schick dir eine PM. (Sonstige Mitleser werden deren Inhalt erfahren, wenn ich das Rätsel mal auflöse, was ich erst mal noch nicht tun will.)



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2018-10-10


Möchte noch jemand an Teil 0 knobeln? Wenn sich niemand meldet, löse ich diesen am Freitag auf.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, vom Themenstarter, eingetragen 2018-10-12


Hier die Lösung zu 0):


Ja, kann man.
Wir betrachten die Morse-Thue-Folge $A, B, B, A, B,A,A,B, B,A,A,B,A,B,B,A, ...$. Diese entsteht induktiv wie folgt: Das erste Glied ist $A$. Wenn die ersten $2^k$ Glieder der Folge schon bekannt sind, dann bekommt man die nächsten $2^k$ Glieder, indem man den Anfang der Folge wiederholt, dabei aber alle $A$'s durch $B$'s ersetzt und alle $B$'s durch $A$'s:
erste Iteration (ein Folgenglied): $A$,
zweite Iteration (die ersten zwei Folgenglieder): $A$, $B$
dritte Iteration: $A, B$,  $B,A$
vierte Iteration: $A,B,B,A$,   $B,A,A,B$
fünfte Iteration: $A,B,B,A,B,A,A,B$  $B,A,A,B,A,B,B,A$

Wir teilen jetzt die Elemente der Menge $\{0,1,\ldots, 14,15\}$ gemäß dieser Folge auf zwei Mengen $A$ und $B$ auf:
\[\begin{matrix} 0&1&2&3 &\ldots &14&15\\
A&B&B&A&\ldots &B&A\end{matrix}\] also $A=\{0,3,5,6,9,10,12,15\}$ und $B=\{1,2,4,7,8,11,13,14\}$. Diese Partition hat die gewünschten Eigenschaften:
\[
\newcommand{\A}[1]{0^{#1}+3^{#1}+5^{#1}+6^{#1}+9^{#1}+10^{#1}  +12^{#1}+15^{#1}}
\newcommand{\B}[1]{1^{#1}+2^{#1}+4^{#1}+7^{#1}+8^{#1}+11^{#1}  +13^{#1}+14^{#1}}


\begin{align*}\A 0&= 8 &= \B 0,\\
\A 1&= 60 &= \B 1,\\
\A 2&= 620 &= \B 2,\\
\A 3&= 7200 &= \B 3.
 \end{align*}\]
Zum ersten Mal gehört habe ich von dieser Eigenschaft in diesem Video.


Es dürfen weiterhin Lösungen für die Aufgaben a) und b) abgegeben werden.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2019-08-01

\(\begingroup\)\( \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Auflösung:


Die Antwort auf a) und b) ist ebenfalls ja. Wir zeigen eine allgemeinere Aussage:

Sei eine ganze Zahl $a\geq 2$ gegeben. Wir definieren rekursiv eine Abbildung $f:\IN \to \IZ/a\IZ$ durch $f(0):=0$ und $f(an+r):=f(n)+r$ für alle $n,r\in \IN, 0\leq r < a$.
Weiter definieren wir für $m,n\in \IN$ und $r\in \IZ/a\IZ$ den Ausdruck
\[
S(m,n,r):= \sum_{\substack{0\leq k < a^n \\ f(k)=r}} k^m.
\] Dann hängt für $m<n$ der Wert von $S(m,n,r)$ nicht von $r$ ab.

Beweis durch vollständige Induktion nach $n$:
Induktionsanfang: Für $n=1$ gilt $S(0,1,r) = 1$.
Induktionsschluss:
Sei $m< n+1$. Es gilt
\[\begin{align*}
S(m,n+1,r)&= \sum_{\substack{0\leq k < a^{n+1} \\ f(k)=r}} k^m\\
&= \sum_{0\leq s < a} \sum_{\substack{0\leq k < a^n \\ f(k)= r-s}} (ak+s)^m\\
&=\sum_{0\leq s < a} \sum_{\substack{0\leq k < a^n \\ f(k)= r-s}} \sum_{0\leq i \leq m}\binom mi(ak)^i s^{m-i}\\
&= \sum_{0\leq i \leq m}\binom mi a^i \sum_{0\leq s < a}s^{m-i} \sum_{\substack{0\leq k < a^n \\ f(k)= r-s}} k^i\\
&= \sum_{0\leq i \leq m}\binom mi a^i \sum_{0\leq s < a}s^{m-i} S(i,n,r-s).
\end{align*}\] Für $i<n$ hängt der Wert von $S(i,n,r-s)$ per Induktionsannahme nicht von $r$ ab.
Wenn $i=n$, dann muss auch $m=n$ sein und es folgt, dass
\[\begin{align*}
 \sum_{0\leq s < a}s^{m-i} S(i,n,r-s) &= \sum_{0\leq s < a}S(n,n,r-s)\\
&= \sum_{0\leq s < a}S(n,n,s)\end{align*}\] nicht von $r$ abhängt. $\square$


Mehr zu diesem Thema findet man z.B. auf Wikipedia und in diesem Artikel.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]