Heuristik, Kombinatorik

11.06.2010, 11:53

kurellajunior

RE: Heuristik, Kombinatorik

Zitat:

Original von 00nele00
Meine Ideen:
Ich hab mir bislang die dreiecke für die einzelnen n angeguckt, die möglich sind und die nicht möglich sind. festzustellen ist nur, dass die dreiecke, die bei n nicht möglich sind, die anzahl derer ist, die bei n+1 möglich sind...mehr hab ich leider nicht...

Kannst Du diese Erkenntnisse mal anfügen? besonders der Teil "die dreiecke, die bei n nicht möglich sind, die anzahl derer ist, die bei n+1 möglich sind..." klingt reichlich verworren.

Also einfach mal auflisten bis n=5 bis dahin sollte es einfach sein, die Dreiecke auszuzählen.

Der Anfang ist einfach:

n=1, n=2 : 0 Dreiecke
n=3: 0 Dreiecke (das Gebilde was man aus den drei Hölzern legen könnte hat keine Flächeninhalt Augenzwinkern

jetzt Du

11.06.2010, 14:52

00nele00

Auf diesen Beitrag antworten »

also n=1 und n=2 fallen ja sowieso weg, dann kommt bei n=3 kein dreieck zustande, wie du schon gesagt hast.

also bei n=3 0dreiecke und 1 welches nicht möglich ist

jetzt zu n=4..insgesamt bei 4 über 3 sinds 4 möglichkeiten, die hölzer auszuwählen. ich weiß ja, dass bei n=3 es 1 dreieckkombination gab, die kein dreieck bilden kann. also weiß ich, dass es bei n=4 eine kombination gibt, die möglich ist: {2,3,4}. und wg 4 (ingesamt möglichkeiten)-1= 3 die wieder nicht gehen : {1,2,3};{1,2,4};{1,3,4}

bei n=5 genauso:
5 über 3= 10 möglichkeiten insgesamt
wieder gilt die anzahl der dreiecke, die bei n=4 NICHT geßing, ist nun die anzhal der dreiecke, die für n=5 geht. also mögliche dreiecke für n=5 ist 3, nämlich: {2,3,4};{2,4,5};{3,4,5} und dann: 10-3=7 (wieder die anzahl der dreiecke, die für n=5 wegfallen)

ist ein wenig schwierig das zu erklären, ich hoff du kommst noch mit?!?

11.06.2010, 16:49

wisili

Auf diesen Beitrag antworten »

Falls du an einer expliziten Formel (ohne Beweis) der Anzahl nichtkongruenter echter Dreiecke mit Umfang n und ganzzahligen Seiten interessiert bist, könntest du mal folgende überprüfen:

$\begin{eqnarray*} Round\left(\frac{(n+3\cdot (n \ mod \ 2))^{2}}{48}\right) \end{eqnarray*}$

Mit detailllierter Herleitung hier.

12.06.2010, 11:11

kurellajunior

Auf diesen Beitrag antworten »

Ja ich kann Dir folgen smile

Lass uns den iterativen Ansatz vertiefen. Vorweg kurz eine Frage, was kann ich voraussetzen? Also welche Klasse bist Du / schätzt Du Dich ein. Kennst Du das Verfahren der vollständigen Induktion?

Kannst Du genau benennen, welche Eigenschaften drei Streichhölzer besitzen müssen, damit man daraus ein Dreieck legen kann?

Erste Überlegung: Wenn ein weiteres Streichholz dazukommt ändert sich an den bisherigen Kombinationen nichts.
Wir brauchen also nur alle Kombinationen zu finden, die mit dem neuen Streichholz gehen und die, die nicht gehen:

n=3: {1,2,3}

n=4: hier brauchen wir nur alle Paare aus {1,2,3} mit 4 zu überprüfen, ob die oben erfragte Bedingung greift. Versuch's mal

12.06.2010, 15:05

00nele00

Auf diesen Beitrag antworten »

Also in einem Dreieck müssen die beiden kürzeren seiten addiert größer sein als die längste Seite.

Das beweisprinzip der vollständigen Induktion ist mir auf jeden fall sehr gut bekannt.

Studiere mathematik. Allerdings steh ich bei der aufgabe wirklich komplett auf dem schlauch.....:-(

naja was mir bislang nur aufgefallen ist, dass halt immer die kombinationen mit {1,x,n} hinzukommen...und alle bis zu dem punkt x+y>n...

allerdings kann ich leider keine regelmäßigkeit feststellen...

13.06.2010, 10:16

kurellajunior

Auf diesen Beitrag antworten »

Ok, super, dann will ich Dir mal zeigen, was ich sehe, vielleicht kommst Du damit weiter:

Ich betrachte die Iteration für $\begin{eqnarray*} a_n \end{eqnarray*}$ wobei $\begin{eqnarray*} a \end{eqnarray*}$ für die Anzahl der gültigen Dreieckskombinationen steht. Start punkt ist $\begin{eqnarray*} n=3 \end{eqnarray*}$ :
$\begin{eqnarray*} (1,2,3) \end{eqnarray*}$

Für das nächste $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ muss ich nur noch die hinzukommenden Tripel untersuchen, dass sind die Kombinationan aus den Tupeln $\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} n+1 \end{eqnarray*}$
(weil ich in Latex hier keine Farben hinbekomme, habe ich die Tupel, die mit dem neuen n+1 ein gültiges Tripel ergeben in eckige Klammern gesetzt unglücklich

)

n=4:
$\begin{eqnarray*} \begin{matrix}(1,2)&(1,3)&4 \\ &[2,3] & 4\end{matrix} \end{eqnarray*}$

n=5
$\begin{eqnarray*} \begin{matrix}(1,2)&(1,3)&(1,4)&5 \\ &(2,3) & [2,4]&5\\&&[3,4]&5\end{matrix} \end{eqnarray*}$

Wenn Du dieses Format weiterspinnst (mindestens bis n=7) solltest Du ein Muster erkennen, dass Du in die Form
$\begin{eqnarray*} a_{n+1}=a_n+? \qquad ;a_3=0 \end{eqnarray*}$
gießen kannst. Da fehlt dann "nur" noch die Umwandlung in die explizite Form und der Beweis. Aber eins nach dem anderen.

Versuch's mal smile

13.06.2010, 12:16

00nele00

Auf diesen Beitrag antworten »

hey, habe das ganze jetzt bis n=10 weiter durchgespielt und man kann sehen, dass die dreiecke, die hinzukommen, folgende reihenfolge verfolgen:

+1,+1,+2,+2,+3,+3,+4,+4......usw

ist es das, worauf du hinauswolltest?

13.06.2010, 12:47

kurellajunior

Auf diesen Beitrag antworten »

So in etwa, aber die Reihe stimmt nicht?
Guck mal für n=6
$\begin{eqnarray*} \begin{matrix}(1,2)&(1,3)&(1,4)&(1,5)&6 \\ &(2,3) & (2,4)&[2,5]&6\\&&[3,4]&[3,5]&6\\&&&[4,5]&6\end{matrix} \end{eqnarray*}$

also $\begin{eqnarray*} n_6 = n_5+4 \end{eqnarray*}$
edit: ah jetzt, Du meinst, wie sich die Zunahme ändert? ja das meinte ich smile

13.06.2010, 13:03

00nele00

Auf diesen Beitrag antworten »

hab mit n=3 angefangen, da sind es ja 0, sprich:
$n_{4}=n_{3}+1
$n_{5}=n_{4}+2
$n_{6}=n_{5}+4
$n_{7}=n_{6}+6
$n_{8}=n_{7}+9
Also beispielsweise bei n=7 sind es ja 6 mögliche Dreiecke, die noch hinzukommen..?

13.06.2010, 13:13

kurellajunior

Auf diesen Beitrag antworten »

Das sieht gut aus smile

Nun musst Du noch diese Reihe (1,2,4,6,9,12,...) formulieren. Schaffst Du das?
PS: Du kannst meine Beiträge zitieren um zu sehen, wie man den LaTeX code hier einfügt smile

13.06.2010, 13:17

00nele00

Auf diesen Beitrag antworten »

ehrlich gesagt, versuch ich das schon die ganze zeit, allerdings hapert es gewaltig...

13.06.2010, 13:46

kurellajunior

Auf diesen Beitrag antworten »

Ich muss jetzt los und bin erst Abends wieder da. hier mein Ansatz bisher - bestimmt kann einer übernehmen.

Ich habe mir dieses Dreieck der gültigen Tupel $\begin{eqnarray*} z \end{eqnarray*}$ angesehen und konnte den Zusammenhang erkennen:

$\begin{eqnarray*} z_{gerade}=\frac{n}{2}\left(\frac{n}{2}+1\right)=\frac{n^2}{4}+\frac{n}{2} \end{eqnarray*}$
$\begin{eqnarray*} z_{ungerade}=\left(\frac{n}{2}+\frac{1}{2}\right)^2=\frac{n^2}{4}+\frac{n}{2}+\frac{1}{4} \end{eqnarray*}$

zusammengefasst wäre das (nicht vergessen, wir sind um 3 versetzt!)
$\begin{eqnarray*} z_{n+3}=\text{rund}\left(\frac{n^2}{4}+\frac{n}{2}\right) \end{eqnarray*}$ Da gibt's bestimmt was besseres, aber hier muss dann jemand anders einspringen.
Das kannst Du nun als Summand für das Fragezeichen oben einsetzen smile

13.06.2010, 19:44

00nele00

Auf diesen Beitrag antworten »

könntest du mir bitte diesen zusammenhang nochmal etwas genauer erklären? ich kann dir leider nicht folgen....wäre super lieb!

13.06.2010, 21:12

kurellajunior

Auf diesen Beitrag antworten »

Ich werd's versuchen Augenzwinkern

Eins vorneweg, ich selbst hatte Mathe nur als Nebenfach im Studium - daher ist das für mich eher eine Knobelaufgabe. Falls es hierfür "bekannte" Namen oder Methoden gibt, müssen wir auf Unterstützung von anderen Experten warten.

Hier mein Weg.
Du erinnerst Dich an die Dreiecke mit den gültigen Tupeln oben? Ich greif mal nur die heraus und zeig Dir wie ich auf die beiden Formeln gekommen bin (die X und O sind beide gültig, nur zur optischen unterscheidung)

ungerade (n gerade)
1: (n=4)
$\begin{eqnarray*} O \end{eqnarray*}$
3: (n=6)
$\begin{eqnarray*} \begin{matrix}&O&\\X&O&O\end{matrix} \end{eqnarray*}$
5: (n=8)
$\begin{eqnarray*} \begin{matrix}&&O&\\&X&O&O\\X&X&O&O&O\end{matrix} \Rightarrow \begin{matrix}O&X&X\\O&O&X\\O&O&O\end{matrix} \end{eqnarray*}$ 3x3-Quadrat : (5/2+1/2)^2

2: (n=5)
$\begin{eqnarray*} \begin{matrix}X&O\end{matrix} \end{eqnarray*}$
4: (n=7)
$\begin{eqnarray*} \begin{matrix}&X&O&\\X&X&O&O\end{matrix} \Rightarrow \begin{matrix}O&X&X\\O&O&X\end{matrix} \end{eqnarray*}$ 2x3 Rechteck: (4/2)^2

War es das, was Du wissen wolltest?

13.06.2010, 21:35

00nele00

Auf diesen Beitrag antworten »

das ist genau das, was ich wissen wollte!!! und ich die formel hab ich schon ganz oft in dem zusammenhang mit der aufgabe gesehen, allerding fehlt mir echt noch die verbindung von quadraten/rechtecken in verbindung mit den streichhölzern!

dafür, dass du mathe "nur" im nebenfach hattest, haste aber echt mal ahnung ;-) das ist definitiv eine richtige knobelaufgabe :-(

vielen lieben dank, dass du dir so viel mühe gibst!!!!

13.06.2010, 21:55

kurellajunior

Auf diesen Beitrag antworten »

Kannst Du denn jetzt die iterative Formel erstellen?

13.06.2010, 22:03

00nele00

Auf diesen Beitrag antworten »

wie biste du denn überhaupt auf die quadrate und rechtecke gekommen und von da aus auf die formel?

13.06.2010, 22:28

kurellajunior

Auf diesen Beitrag antworten »

Also zuerst wollte ich das Grundproblem iterativ lösen - also habe ich mir nur die Tripel angesehen, die dazu kommen.
Dabei ist mir aufgefallen, dass ja immer die größte Zahl dazukommt, ich also nur all Paare darunter prüfen muss, ob ihre Summe größer der neuen Zahl sind.

Das habe ich aufgemalt und die gültigen Tripel unterstrichen, dabei sind mir die Dreiecke aufgefallen.

Diese habe ich dann eine Weile betrachtet, verschieden gemalt, in ein Koordinatensystem geschrieben, bis ich auf die Idee gekommen bin, die ungeraden und geraden getrennt zu betrachten.
Da war es ganz einfach ein Quadrat und ein Rechteck zu sehen (ich habe viele Zerlegerätsel gemacht und Faible dafür)
Die beiden Formeln unterschieden sich dann nur in dem letzten Summand $\begin{eqnarray*} \frac{1}{4} \end{eqnarray*}$ also kann man das runden Augenzwinkern

Du müsstest jetzt aber noch das $\begin{eqnarray*} f(n) \end{eqnarray*}$ aus unseren Bisherigen Überlegungen in $\begin{eqnarray*} a_{n+1}=a_n+f(n) \end{eqnarray*}$ füllen, damit wir weiter überlegen können - oder reicht die iterative Formel?
PS ich bin erstmal im Bett. Entweder jemand übernimmt, oder morgen weiter smile

Neue Frage »

Antworten »

Heuristik, Kombinatorik

Verwandte Themen