Produkt aus glatten Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe folgende Aufgabe:
Eine natürliche Zahl n heißt glatt bezüglich einer Schranke S, wenn in der Primfaktorzerlegung von n keine Primzahlen größer als S vorkommen.
Gegeben sei nun eine Menge von 2000 glatten Zahlen bezüglich der Schranke 19. Ich soll zeigen, dass es dann möglich ist, aus dieser Menge 8 Zahlen auszuwählen, sodass deren Produkt die 8. Potenz einer ganzen Zahl ist.
Was ich bisher herausgefunden habe, ist, dass ich, wenn ich zwei Zahlen auswählen will, sodass deren Produkt ein Quadrat ist, so muss meine Menge mindestens 257 Zahlen umfassen, denn es gibt 8 Primzahlen, die kleiner/gleich 19 sind. Betrachte ich die Exponenten in der Primzahlzerlegung modulo 2, so gibt es [mm] 2^8 [/mm] verschiedene Kombinationen von Primzahlexponenten. Nehme ich einen mehr, habe ich mindestens 2 Zahlen, mit der gleichen Primzahlkombination modulo 2. Multipliziere ich diese, erhalte ich ein Quadrat.
Mir ist es nur noch nicht gelungen, dieses Konzept von 2 auf 8 zu erhöhen, ohne dabei viel mehr als 2000 Zahlen zu benötigen. Hat jemand einen Tipp?
LG
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:15 Do 19.09.2013 | | Autor: | felixf |
Moin!
> ich habe folgende Aufgabe:
>
> Eine natürliche Zahl n heißt glatt bezüglich einer
> Schranke S, wenn in der Primfaktorzerlegung von n keine
> Primzahlen größer als S vorkommen.
>
> Gegeben sei nun eine Menge von 2000 glatten Zahlen
> bezüglich der Schranke 19. Ich soll zeigen, dass es dann
> möglich ist, aus dieser Menge 8 Zahlen auszuwählen,
> sodass deren Produkt die 8. Potenz einer ganzen Zahl ist.
Ich vermute, die Zahlen sollen jeweils paarweise verschieden sein?
> Was ich bisher herausgefunden habe, ist, dass ich, wenn ich
> zwei Zahlen auswählen will, sodass deren Produkt ein
> Quadrat ist, so muss meine Menge mindestens 257 Zahlen
> umfassen, denn es gibt 8 Primzahlen, die kleiner/gleich 19
> sind. Betrachte ich die Exponenten in der Primzahlzerlegung
> modulo 2, so gibt es [mm]2^8[/mm] verschiedene Kombinationen von
> Primzahlexponenten. Nehme ich einen mehr, habe ich
> mindestens 2 Zahlen, mit der gleichen Primzahlkombination
> modulo 2. Multipliziere ich diese, erhalte ich ein Quadrat.
Genau.
> Mir ist es nur noch nicht gelungen, dieses Konzept von 2
> auf 8 zu erhöhen, ohne dabei viel mehr als 2000 Zahlen zu
> benötigen. Hat jemand einen Tipp?
Du hast ja praktisch folgendes Problem: gegeben sind 2000 Elemente [mm] $v_1, \dots, v_{2000}$ [/mm] aus $X := [mm] (\IZ/8\IZ)^8$. [/mm] Gesucht sind jetzt acht verschiedene Indices [mm] $i_1, \dots, i_8$ [/mm] mit [mm] $\sum_{j=1}^8 v_{i_j} [/mm] = 0$. Insgesamt hat $X$ nun [mm] $8^8 [/mm] = [mm] 2^{3 \cdot 8} [/mm] = [mm] 2^{24}$ [/mm] Elemente, was wesentlich mehr 2000 ist.
Wenn du vier Elemente aus [mm] $v_1, \dots, v_{2000}$ [/mm] addierst, gibt es dafuer [mm] $\binom{2000}{4}$ [/mm] Moeglichkeiten. Das ist groesser als $39617 [mm] \cdot [/mm] |X|$, also sehr gross im Vergleich zu [mm] $8^8 [/mm] = |X|$. Damit kannst du vielleicht zeigen, dass es zwei disjunkte(!) vierelementige Teilmengen von [mm] $\{ 1, \dots, 2000 \}$ [/mm] geben muss, deren zugehoerige Summen jeweils zusammenaddiert 0 ergeben.
(Das es zwei solche Teilmengen gibt, die moeglicherweise jedoch nicht disjunkt sind, ist einfach zu zeigen.)
LG Felix
|
|
|
| |
|
Danke für deine Antwort!
"(Das es zwei solche Teilmengen gibt, die moeglicherweise jedoch nicht disjunkt sind, ist einfach zu zeigen.) "
Noch nicht einmal das sehe ich gerade einfach so :( Ich sehe gerade überhaupt nicht, wie man überhaupt mit Sicherheit auch nur eine vierelementige Teilmenge [mm] $\{i_1,i_2,i_3,i_4\}$ $\subset \{1, ..., 2000\}$ [/mm] nehmen kann, sodass [mm] $v_{i_1}+v_{i_2}+v_{i_3}+v_{i_4} [/mm] = 0$. Wenn das ginge, könnte man dann nicht das gleiche Argument benutzen, um aus den [mm] $\binom{2000}{8}$ [/mm] möglichen Summen aus 8 Summanden, eine solche rauszusuchen, sodass deren Summe gleich 0 ist? Da gibt es ja noch viel mehr Möglichkeiten.
Oder habe ich da ein enormes Brett vorm Kopf? Vielleicht ist es auch schon etwas spät, um etwas sinnvolles zu leisten.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:47 Fr 20.09.2013 | | Autor: | felixf |
Moin!
> Danke für deine Antwort!
>
> "(Das es zwei solche Teilmengen gibt, die moeglicherweise
> jedoch nicht disjunkt sind, ist einfach zu zeigen.) "
Ah, ganz so einfach ist das doch wieder nicht 
> Noch nicht einmal das sehe ich gerade einfach so :( Ich
> sehe gerade überhaupt nicht, wie man überhaupt mit
> Sicherheit auch nur eine vierelementige Teilmenge
> [mm]\{i_1,i_2,i_3,i_4\}[/mm] [mm]\subset \{1, ..., 2000\}[/mm] nehmen kann,
> sodass [mm]v_{i_1}+v_{i_2}+v_{i_3}+v_{i_4} = 0[/mm]. Wenn das ginge,
Ich hab nicht nach $= 0$ gesucht, sondern nach zwei solchen Teilmengen die die gleiche Summe (modulo 8) liefern. Damit kommt man aber nicht direkt weiter.
So wie du es gemacht hast, ist es am einfachsten und funktioniert auch ohne viel Aufwand
LG Felix
|
|
|
| |
|
Ich habe es inzwischen gelöst. Hat man mehr als 257 Zahlen, so lassen sich ja zwei finden, deren Produkt eine Quadratzahl ist. Nun nimmt man diese beiden Zahlen aus der Menge heraus und wiederholt diesen Vorgang, bis nur noch 255 Zahlen in der Menge enthalten sind. Auf diese Weise hat man dann eine neue Menge aus Quadratzahlen generiert, auf die man wieder das gleiche Verfahren anwendet. Auf diese Weise gelangt man zur Lösung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:45 Fr 20.09.2013 | | Autor: | felixf |
Moin!
> Ich habe es inzwischen gelöst. Hat man mehr als 257
> Zahlen, so lassen sich ja zwei finden, deren Produkt eine
> Quadratzahl ist.
Es reicht schon, wenn es mehr als 256 sind.
> Nun nimmt man diese beiden Zahlen aus der
> Menge heraus und wiederholt diesen Vorgang, bis nur noch
> 255 Zahlen in der Menge enthalten sind. Auf diese Weise hat
> man dann eine neue Menge aus Quadratzahlen generiert, auf
Und zwar $(2000 - 256) / 2 = 872$ Stueck.
> die man wieder das gleiche Verfahren anwendet.
Im naechsten Schritt bleiben $(872 - 256) / 2 = 308$ vierte Potenzen, und daraus kann man sogar $(308 - 256) / 2 = 26$ verschiedene achte Potenzen bekommen.
> Auf diese
> Weise gelangt man zur Lösung.
Sieht gut aus :)
LG Felix
|
|
|
|
