Mathematische Knobelaufgaben

nagel · Beiträge: 708 Win7, Ubuntu 10.10

Hat's jemand geschafft, die Lösung der x^(x^(...)-Aufgabe streng zu beweisen?
Die Lösung ist zwar leicht zu erraten und auch irgendwie intuitiv begründbar, aber ein richtiger Beweis ist mir noch nicht eingefallen.

Kha · Verfasst: Sa 25.10.08 12:45

Grenzwertbestimmung der Oberstufe:

markieren

Quelltext

1:
2:
3:

a_n = a_(n-1)
x^g = g      ; g = 2
...

Fehlt nur noch der Beweis, dass die Folge auch wirklich konvergiert, aber der ist trivial.

_________________
>λ=

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hidden hat folgendes geschrieben :

Hi,

[OT?]
Was auf jeden Fall Laufzeitmäßig ganz dolle hilft, ist, den Ring mit z.B. 32 zu beginnen. Dann kann er nämlich nur mit zwei Zahlen Enden(49-32=17 und 36-32=4). Da die zweite Form die Inverse der ersten sein muss, kann man es auf eine reduzieren und muss in den Blättern nurnoch auf eine Quadratzahl prüfen, wenn es darum geht, den Ring zu schließen(letzte Zahl + Erste Zahl = 49).

Habe ich so noch nicht drin, ich arbeite momentan mit 36 und 49 und habe deshalb noch eine Abfrage mit Sets da.. Ich ändere das mal gerade und sehe, was es bringt.

mfG,

Hab ich auch gedacht

Mein Programm basiert halt auf einem Graphen bei dem z.B. die Kanten (1, 3), (1,

etc. existieren, in dem ich dann einen Hamiltonkreis suche.
Ich hab die Adjazenzlisten mal aufsteigend nach dem Grad der adjazenten Knoten sortiert, bei n=32 führte das zu unter 1000 Rekursionen, die Rechenzeit für n=64 stieg jedoch enorm an

der organist · Verfasst: Sa 25.10.08 19:54

andererseits kann man die 1-32 Aufgabe auch wie die Gefnagenenaufgabe angehen, da mein ja weiss, dass es sich um einen Kreis handelt...was ich aber bisher nicht sonderlich erfolgreich vertiefen konnte.

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

der organist hat folgendes geschrieben :

andererseits kann man die 1-32 Aufgabe auch wie die Gefnagenenaufgabe angehen, da mein ja weiss, dass es sich um einen Kreis handelt...was ich aber bisher nicht sonderlich erfolgreich vertiefen konnte.

Das Problem ist ja gerade dass es sich um einen Kreis handelt, deswegen wird das nix...

Hidden · Verfasst: So 26.10.08 09:02

Da es Zahlen gibt, die nur zwei Partner haben, handelt es sich um ein 1D-Puzzle. Draußen in RL werden 3D-Puzzles gelöst, da sollte das doch kein Problem sein :mrgreen:

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

der organist · Verfasst: So 26.10.08 10:50

Thorsten83 hat folgendes geschrieben :

der organist hat folgendes geschrieben :

andererseits kann man die 1-32 Aufgabe auch wie die Gefnagenenaufgabe angehen, da mein ja weiss, dass es sich um einen Kreis handelt...was ich aber bisher nicht sonderlich erfolgreich vertiefen konnte.

Das Problem ist ja gerade dass es sich um einen Kreis handelt, deswegen wird das nix...

was meinst du, wie ich heute diese Aufgabe gelöst habe? {EDIT: kleines Missverständnis} Ich hab mal zwei Bilder angehangen, wo (a) interessante Zeichnungen zur Lösung sind und (b) auch die Lösung. Alle die die Lösung selber finden wollen oder gar nicht wissen wollen, sollten nicht diese Bilder ansehen.

markieren

Delphi-Quelltext

1:	//EDIT: Mache ich doch besser erst, wenn die Preisfrage abgelaufen ist...

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Horst_H · Verfasst: So 26.10.08 15:33

Hallo,
eine kleine Ergänzung:
Rekursionstiefe und Anzahl der Aufrufe sind zwei verschiedene Dinge.Bei 1..32 ist die Rekursionstiefe 2 und die Anzahl der Rekursionsaufrufe 73 .
Ich habe mal 1..49 gerechnet, das ist ja unabhängig von 1..32-Problem:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

58225 Rekursionsaufrufe:
4->32->49->15->1->3->6->10->26->23->41->40->24->25->39->42->22->27->37->12->13->
36->45->19->30->34->47->17->8->28->21->43->38->11->14->2->7->9->16->48->33->31->
18->46->35->29->20->44->5 (fehlt ->4 )
bei 54 sind 205609 Rekursionsaufrufe bis zur ersten Lösung 
der Gag:
bei 58 
13 Rekursionsaufrufe                                                                           
4->12->37->44->56->25->39->42->22->27->54->10->6->58->23->41->40->24->57->43->21
->28->36->13->51->30->19->45->55->26->38->11->53->47->34->15->49->32->17->8->1->
3->33->48->52->29->35->46->18->31->50->14->2->7->9->16->20->5

Mein Program versucht zuerst jeder Zahl zwei Nachbarn zuzuordnen und testet dann auf Hamilton-Kreis.
Bei 64 versagt es kläglich, es dauert ewig, bei 1..70 wieder nach ~406000 Rekursionen

Scheinbar gibt es immer nur eine eindeutige Lösung.
Warum ist das so und wie ist das zu nutzen.

Gruß Horst

der organist · Verfasst: Mo 27.10.08 20:39

Horst_H hat folgendes geschrieben :

[...]
Scheinbar gibt es immer nur eine eindeutige Lösung.
Warum ist das so und wie ist das zu nutzen.
[...]

Mal abgesehen von der spiegelsymmetrischen Lösung. Eigentlich sollte man aber schon nach n! Versuchen aufhören können.

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Horst_H · Verfasst: Mo 27.10.08 21:17

Hallo,

Zitat:

Eigentlich sollte man aber schon nach n! Versuchen aufhören können.

32! = 2,6313083693369353016721801216e+35 bezogen auf was.
Wegen des Kreises gibt es keine eindeutige Startposition bleiben also 31!

Die 1 hat 4 mögliche Nachbarn, die 32 und 9 weitere deren 2. Aber das hatten wir schon.
Die maximale Anzahl wäre also 4^(32-10) =1,7592186044416e+13
Meine Rekursion ist jetzt nach 62xxx Rekursionsaufrufen komplett fertig.

Bleibt trotzdem die Frage: gibt wirklich nur eine Lösung (wegen mir gespiegelt und an irgendeinem anderen Feld begonnen, ich hab wegen der Aufgabe 4 gewählt) und kann man diesen Kreis erst mit n beginnt nur für n>= 32 bilden.
(Man muss ja mindestens 2 Quadratzahlen > 2*n-1, wobei aber 18 (18+18 = 36 geht ja nicht) um 49 zu erreichen eine 31 braucht. Aber mit n= 31 bekomme ich den Kreis nicht hin)

Gruß Horst

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Ja gut, die "verschobenen" Lösungen sind ja eigentlich identisch, da es sich um einen Kreis handelt...

Der Organist und ich haben eben festgestellt dass wir unterschiedliche Lösungen haben, ich hab in meiner keinen Fehler gesehen und seine soll wohl auch richtig sein.

Ich werd mein Programm nachher mal ein bißchen pimpen, mal gucken was es dann so für Lösungen ausspuckt...

edit:
Für n=34 finde ich schon 22 Lösungen, also 11 und jeweils dazu das symmetrischen Pendant.

edit2:
n = 32
Ergebnisse: 2

n = 33
Ergebnisse: 2

n = 34
Ergebnisse: 22

n = 35
Ergebnisse: 114

n = 36
Ergebnisse: 62

n = 37
Ergebnisse: 40

n = 38
Ergebnisse: 50

n = 39
Ergebnisse: 100

n = 40
Ergebnisse: 128

n = 41
Ergebnisse: 928

n = 42
Ergebnisse: 2124

n = 43
Ergebnisse: 8674

n = 44
Ergebnisse: 20182

n = 45
Ergebnisse: 43862

Horst_H · Verfasst: Di 28.10.08 11:51

Hallo,

uups, da habe ich in meinem Programm einmal zuviel die Lösungszahl reduziert, weshalb immer nur die erste ausgespuckt wurde...
Mein Verfahren ist aber sehr langsam, obwohl es zufälligerweise öfter schnell eine erste Lösung findet.

Gruß Horst

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

die Geschwindigkeit schwankt bei mir auch extrem, hab mal die Adjazenzlisten sortiert und die Zeit für n=64 stieg von 14 Sekunden auf 40 Minuten

der organist · Verfasst: Di 28.10.08 17:14

Thorsten83 hat folgendes geschrieben :

[...]

edit:
Für n=34 finde ich schon 22 Lösungen, also 11 und jeweils dazu das symmetrischen Pendant.

[...]

n = 40
Ergebnisse: 128

n = 41
Ergebnisse: 928

n = 42
Ergebnisse: 2124

n = 43
Ergebnisse: 8674

n = 44
Ergebnisse: 20182

n = 45
Ergebnisse: 43862

Ich hab keine Ahnung, was dein Programm macht, etc andere Umstände, aber mein Gefühl sagt mir, dass es nicht so viele Lösungen geben kann...Ich mag mich irren.

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Horst_H · Verfasst: Di 28.10.08 17:38

Hallo,

was spricht dagegen?
Bei 34 habe ich auch 11 Lösungen, das andere dauert mir zu lange.
Wenn man sich die Lösungen anschaut wird ein Kreisabschnitt neu kombiniert, sodass deren Start und Endnachbarn die gleichen bleiben.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

n= 34:
Lösung
1
4->32->17->19->6->30->34->2->14->22->27->9->16->20->29->7->18->31->33->3->1->8-
28->21->15->10->26->23->13->12->24->25->11->5
2 zu Lösung 1
4->32->17  ->8->28->21->15->1->3->33->31->18->7->29->20->16->9->27->22->14->2->34-
>30->19->6->  10->26->23->13->12->24->25->11->5
3 zu Lösung 1
4->32->17->19->  30->6->10->26->23->2->34->15->21->28->8->1->3->13->12->24->25->11
->14->22->27->9->16->33->31->18->7->29->20  ->5
4 zu Lösung 3
4->32->17->19->30->6->10->26->23->  13->12->24->25->11->14->2->34->15->21->28->8->
1->3  ->22->27->9->16->33->31->18->7->29->20->5
5 zu Lösung 1
4->32->17->19->6->30->34->2  ->23->26->10->15->21->28->8->1->3->13->12->24->25->11
->14->22->27->9->16->33->31->18->7->29->20->  5
6 zu Lösung 1
4->32->17->19->6->30->34->2->14->  11->25->24->12->13->23->26->10->15->21->28->8->
1->3->22->27->9->16->33->31->18->7->29->20  ->5
7 zu Lösung 4
4->32->17->19->30->6->10->26->23->13->  3->1->8->28->21->15->34->2->14->22->27->9-
>16->33->31->18->7->29->20->5->11->25->24->12

8 ....
4->32->17->19->6->30->34->  15->10->26->23->2->14->22->27->9->16->33->31->18->7->2
9->20->5->11->25->24->12->13->3->1->8->28->21
9
4->32->17->19->30->34->15->21->28->8->1->24->25->11->5->20->29->7->18->31->33->1
6->9->27->22->14->2->23->26->10->6->3->13->12
10
4->32->17->8->28->21->15->34->30->19->6->10->26->23->2->14->22->27->9->16->33->31
->18->7->29->20->5->11->25->24->1->3->13->12
11
4->32->17->8->28->21->15->1->3->13->23->26->10->6->19->30->34->  2->14->22->27->9-
>16->33->31->18->7->29->20->5->11->25->24->12

Rekursionsaufrufe
1.737.773.518

Was spricht dagegen, dass mit zunehmenden n die Möglichkeiten zunehmen und das sehr moderat.
40!/34! ist ja schon 2,7636336e+9

Gruß Horst

der organist · Verfasst: Di 28.10.08 18:15

(a) Für den Fall, dass das falsch rübergekommen ist...ich zweifle nicht an deinen Fähigkeiten als Programmierer oder als [was weiss ich]
(b) Es gibt zwar viele Möglichkeiten, wie man die Zahlen zusammenfügen kann [n!-symmetrische Lösungen], aber um das ganze mit der Quadratzahlbedingung zusammenzusetzen, dafür klingt es einfach zu viel, weil man nicht jede mit jeder Zahl kombinieren kann.

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin

Horst_H · Verfasst: Di 28.10.08 19:10

Hallo,

was soll ich darauf antworten:

Zitat:

(b) Es gibt zwar viele Möglichkeiten, wie man die Zahlen zusammenfügen kann [n!-symmetrische Lösungen], aber um das ganze mit der Quadratzahlbedingung zusammenzusetzen, dafür klingt es einfach zu viel, weil man nicht jede mit jeder Zahl kombinieren kann.

Es bleiben doch offensichtlich von den n! Möglichkeitenn Zahlen anzuordnen extrem wenige übrig.
Deshalb klingt das eben einfach nicht zu viel.
Das Beispiel mit n=34 sollte es jetzt nur bildhaft dartstellen, wie das aussieht.

Es steigt ja auch die Anzahl der möglichen Nachbarn
Bei n= 33 gibt es im Mittel 2,97 mögliche Nachbarn pro Zahl
Bei n= 34 gibt es im Mittel 3,05 mögliche Nachbarn pro Zahl
..
Bei n= 45 gibt es im Mittel 3,55 mögliche Nachbarn pro Zahl
..
Bei n= 64 gibt es im Mittel 4,32 mögliche Nachbarn pro Zahl
..
Bei n= 128 gibt es im Mittel 5,32 mögliche Nachbarn pro Zahl

Gruß Horst

GTA-Place · Verfasst: Sa 08.11.08 18:16

Mal was zwischendrin:

a1 = 0
a2 = 1
a3 = 4
a4 = 17
a5 = 86
a6 = 517
a7 = 3620
a8 = 28961

Wie lautet die Funktion, bzw. die explizite Angabe der Folge? Ich hab bisher keine Lösung gefunden. Es gibt bestimmt eine, aber ich hab keine Ahnung, wie kompliziert die ist. Vielleicht seid ihr ja schlauer :mrgreen:

Achja, die rekursive Angabe lautet:

u(n) = u(n - 1) * n + 1

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Hidden · Verfasst: Sa 08.11.08 18:30

Hi,

Das "+ 1" lässt sich ja schonmal mit "+ n", bzw. mit "+ n - 1" vom rekursiven ins absolute überführen.

Das u(n - 1) müsste sich doch jetzt auf die e-Funktion zurückführen lassen :gruebel:

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

Kha · Verfasst: Sa 08.11.08 18:45

Hidden hat folgendes geschrieben :

Das "+ 1" lässt sich ja schonmal mit "+ n", bzw. mit "+ n - 1" vom rekursiven ins absolute überführen.

Die Summanden einzeln zu überführen sollte doch nur funktionieren, wenn u(n-1) ohne Koeffizient wäre?
Ich habe nicht viel Hoffnung, dass das etwas wird, wenn nicht jemand eine fertige Formel ausgräbt

.

_________________
>λ=

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme