Spezielle Permutation

29.06.2020, 19:09

Dopap

Spezielle Permutation

kann man zu jedem $\begin{eqnarray*} n>4 \end{eqnarray*}$ bzw. der Menge $\begin{eqnarray*} \{1,2, \cdots ,n\} \end{eqnarray*}$ ein Permutationstupel $\begin{eqnarray*} P^{*}(n) = ( x_1,x_2,x_3, \cdots ,x_n) \end{eqnarray*}$ derart finden,

dass das arithmetische Mittel zweier Zahlen $\begin{eqnarray*} \frac {x_i+x_j}{2},\,\, i<j \end{eqnarray*}$ kein Element der Menge $\begin{eqnarray*} \{x_i, \cdots ,x_j\} \end{eqnarray*}$ ist?

Beispiel: (5,1,3,2,4) erfüllt dies, z.B. (5,3,2,1,4) nicht.

In der "Hälfte" der möglichen Fälle ist das AM keine natürliche Zahl und scheidet aus, was aber nicht wirklich weiter hilft.

Wenn überhaupt müsste das mit vollständiger Induktion zu beweisen sein.

Ein Induktionsanfang mit k=5 ist also schon mal gemacht. Augenzwinkern

Unter der Annahme, dass $\begin{eqnarray*} P^{*}(k) \end{eqnarray*}$ existiert müsste man zeigen, dass dann auch ein $\begin{eqnarray*} P^{*}(k+1) \end{eqnarray*}$ existiert.
Die Frage ist nur wie?

29.06.2020, 20:09

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Spezielle Permutation

Zitat:

Original von Dopap

kann man zu jedem $\begin{eqnarray*} n>4 \end{eqnarray*}$ bzw. der Menge $\begin{eqnarray*} \{1,2, \cdots ,n\} \end{eqnarray*}$ ein Permutationstupel $\begin{eqnarray*} P^{*}(n) = ( x_1,x_2,x_3, \cdots ,x_n) \end{eqnarray*}$ derart finden,

dass das arithmetische Mittel zweier Zahlen $\begin{eqnarray*} \frac {x_i+x_j}{2},\,\, i<j \end{eqnarray*}$ kein Element der Menge $\begin{eqnarray*} \{x_i, \cdots ,x_j\} \end{eqnarray*}$ ist?

Beispiel: (5,1,3,2,4) erfüllt dies, z.B. (5,3,2,1,4) nicht.

Damit die Frage einen Sinn hat, sollte man sie vielleicht so verbessern:

Zitat:

verbesertes Original von Dopap

kann man zu jeder Folge $\begin{eqnarray*} (1,2, \cdots ,n),\; n>4 \end{eqnarray*}$ ein Permutationstupel $\begin{eqnarray*} P^{*}(n) = ( x_1,x_2,x_3, \cdots ,x_n) \end{eqnarray*}$ derart finden,

sodaß für alle $\begin{eqnarray*} 1\le i<j\le n \end{eqnarray*}$ das arithmetische Mittel zweier Zahlen $\begin{eqnarray*} \frac {x_i+x_j}{2},\,\, \end{eqnarray*}$ kein Glied der Teilfolge $\begin{eqnarray*} (x_i, \cdots ,x_j) \end{eqnarray*}$ ist?

Beispiel: (5,1,3,2,4) erfüllt dies, z.B. (5,3,2,1,4) nicht.

29.06.2020, 22:38

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Spezielle Permutation
Um mir Übersicht zu verschaffen, habe ich dazu ein Matlab- Program geschrieben. Dabei habe ich festgestellt, daß mit zunehmenden n auch die Anzahl derjenigen Permutationen zunimmt, für die die Bedingung von Dopap erfüllt ist.

$\begin{eqnarray*} \begin{array}{ll} n & \text{Anz der Permutationen} \\ 5 & 20 \\ 6 & 48 \\ 7 & 104 \\ 8 & 282 \\ 9 & 496 \\ 10 & 1066\end{array} \end{eqnarray*}$

Für n = 5 hat man also die folgenden 20 Permutationen. Vielleicht würde es als Beweisidee helfen, die Zahlen dual dazustellen und sich dann Gesetzmäßigkeiten zu überlegen, wie sich die Ziffern anordnen.
5 1 3 4 2
5 1 3 2 4
4 5 2 1 3
4 2 5 1 3
4 2 3 5 1
4 2 3 1 5
4 2 1 5 3
3 5 4 1 2
3 5 1 4 2
3 5 1 2 4
3 1 5 4 2
3 1 5 2 4
3 1 2 5 4
2 4 5 1 3
2 4 3 5 1
2 4 3 1 5
2 4 1 5 3
2 1 4 5 3
1 5 3 4 2
1 5 3 2 4

code:

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:

function L = per(n)
%29.6.2020 Permutationen danach durchsuchen, ob das Mittel eines 
%Paars von Werten in den Zwischengliedern enthalten ist.
%n = Länge der Folge von 1:n; n < 16
L=[];
if n > 15
    error('Fehler: n >= 16')
end
p=perms(uint32(1:n));
s=size(p,1);
for k = 1:s
    ex=false;
    for a=1:n-1
        for b=a+1:n
            m=p(k,a)+p(k,b);
            for l=a+1:b-1
                if 2*p(k,l)==m
                    ex=true;
                    break
                end
            end
            if ex
                break
            end
        end
        if ex
            break
        end
    end
    if ~ex
        L=[L;p(k,:)];            
    end
end
end

29.06.2020, 22:48

Leopold

Auf diesen Beitrag antworten »

Dopap hat eine alte Aufgabe aus dem Bundeswettbewerb Mathematik ausgegraben. Siehe hier unter dem Jahr 2005.

30.06.2020, 07:35

Dopap

Auf diesen Beitrag antworten »

Aufgaben haben oft verschiedene Quellen.
Aber leider bisher keine Lösung unter dem angegebenen Link gefunden.

@Ullrich Ruhnau: dass meine Formulierung der Aufgabe keinen Sinn ergibt, ist schon ein wenig hart formuliert.
Die Anzahl der passenden Permutationen steigt also an. Die relative Häufigkeit fällt hingegen wie auch eine kleine Simulation zeigte.
Andere Frage: welche Bedeutung haben "ex" und "break" in Matlab?

30.06.2020, 10:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Aber leider bisher keine Lösung unter dem angegebenen Link gefunden.

https://www.mathe-wettbewerbe.de/bwm/auf...loes_05_1_e.pdf

Tatsächlich ist der Nachweis, dass es mindestens eine solche Permutation gibt wohl um einiges einfacher, als eine passende Anzahlformel dafür zu finden. smile

05.07.2020, 08:14

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Andere Frage: welche Bedeutung haben "ex" und "break" in Matlab?

ex hat keine besesondere Bedeutung in Matlab und stellt in meinem Programm nur eine boolsche Variable dar, die angibt, ob die gerade untersuchte Permutation der Bedingung genügt (false) oder nicht (true). Die Tilde negiert diese Variable (~ex).

break ist ein Matlab-Befehl, der Matlab anweist, die innerste Schleife zu verlassen. Hier geht es darum, daß ggf. alle Schleifen bis auf die äußerste verlassen werden, was ich mithilfe der Variablen ex erreiche.

a steht für die Position des ersten Wertes (i), b steht für die Position des zweiten Wertes (j).

05.07.2020, 08:42

Dopap

Auf diesen Beitrag antworten »

verstehe,

THEN und evtl. ELSE "schenkt" sich matlab anscheinend.

Eine Zählschleife vorher zu verlassen ist nMn nicht sauber.
Zählende und/oder Abbruch sollte in einer DO ... UNTIL ... END in die Until-End-Bedingung.

Insgesamt aber ein ziemlich kompakter Code. Augenzwinkern

05.07.2020, 13:25

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
THEN und evtl. ELSE "schenkt" sich matlab anscheinend.

Nein! else gibt es auch in Matlab, war hier aber nicht notwendig.

Zitat:

Eine Zählschleife vorher zu verlassen ist nMn nicht sauber.

Was soll man denn machen? Wenn ich mit k von einer Permutation zur nächsten laufe, dann prüfe ich mit a und b so lange Teilfolgen durch, bis ich eine finde, wo das Abbruchkriterium erfüllt ist und muß andere Teilfolgen nicht mehr untersuchen.

Zitat:

Zählende und/oder Abbruch sollte in einer DO ... UNTIL ... END in die Until-End-Bedingung.

Wir haben hier Matlab und nicht Pascal.

Zitat:

Insgesamt aber ein ziemlich kompakter Code. Augenzwinkern

Matlab steht für Matritzenlabor. Z.B. steht meine Variable p für eine $\begin{eqnarray*} n!\times n \end{eqnarray*}$ -Matrix die alle Permutationen enthält.

Neue Frage »

Antworten »

Spezielle Permutation

Verwandte Themen