Μεταθέσεις και διαφορές

#1

Με αφορμή το θέμα που απαντήθηκε εδώ:

Για ποιες τιμές του θετικού ακέραιου

υπάρχει μετάθεση $\displaystyle{\left\{ {{a_1},{a_2}, \ldots ,{a_n}} \right\}}$ του συνόλου $\displaystyle{\left\{ {1,2, \ldots ,n} \right\}}$ τέτοια, ώστε οι αριθμοί $\displaystyle{\left| {{a_k} - k} \right|,}$ με $\displaystyle{k \in \left\{ {1,2, \ldots ,n} \right\},}$ να είναι ανά δύο διαφορετικοί μεταξύ τους;

#2

Επαναφορά!

#3

Οι αριθμοί της μορφής |a_k - k|

ανήκουν ασφαλώς στο σύνολο $\{0,1,2,\ldots,n-1\}$ και εφόσον είναι διαφορετικοί μεταξύ τους ισούνται με τους αριθμούς $0,1,2,\ldots,n-1$ με κάποια σειρά.

Παρατηρούμε ότι $\displaystyle{ \sum_{k=1}^n |a_k - k| \equiv \sum_{k=1}^n (a_k - k) \equiv 0 \bmod 2. }$

Επειδή όμως $\displaystyle{ 0+1+2+\cdots + (n-1) = \frac{n(n-1)}{2}}$

πρέπει 4|n(n-1)

ή ισοδύναμα $n \equiv 0,1 \bmod 4$ .

Ως εδώ όλα καλά και «απλά». Θα δείξουμε τώρα ότι για όλα αυτά τα

υπάρχει τέτοια μετάθεση. Αυτό το κομμάτι τελικά βγήκε ποιο δύσκολο από ότι υπολόγιζα. (Γι' αυτό μεταφέρω και σε διαφορετικό φάκελο.) Έχει κάποιος κάτι πιο «εύκολο»;

Περίπτωση 1: Αν n=4k

τότε παίρνουμε την εξής μετάθεση

Ξεκινάμε με τα $4k,4k-1,\ldots,3k+1$ , συνεχίζουμε με τα $3k-1,3k-2,\ldots,2k+1$ , μετά βάζουμε το

, μετά συνεχίζουμε με τα $2k,\ldots,k+2$ , μετά το

και τελικά τα $k+1,k,\ldots,2$ .

Οι απόλυτες τιμές των διαφορών ξεκινούν με $4k-1,4k-3,\ldots,2k+1$ , συνεχίζουν με $2k-2,2k-4,\ldots,2$ μετά εμφανίζεται το 2k-1

μετά συνεχίζουν με $1,3,\ldots,2k-3$ , μετά το

και τελικά τα $2k,2k+2,\ldots,4k-2$ .

Περίπτωση 2: Αν n=4k+1

τότε παίρνουμε την εξής μετάθεση

Ξεκινάμε με τα $4k+1,4k,\ldots,3k+2$ , συνεχίζουμε με τα $3k,3k-1,\ldots,2k+1$ , μετά βάζουμε το

, μετά συνεχίζουμε με τα $2k,\ldots,k+2$ , μετά το 3k+1

και τελικά τα $k+1,k,\ldots,2$ .

Οι απόλυτες τιμές των διαφορών ξεκινούν με $4k,4k-2,\ldots,2k+2$ , συνεχίζουν με $2k-1,2k-3,\ldots,1$ μετά εμφανίζεται το

μετά συνεχίζουν με $2,4,\ldots,2k-2$ , μετά το

και τελικά τα $2k+1,2k+3,\ldots,4k-1$ .

Μεταθέσεις και διαφορές

Μεταθέσεις και διαφορές

Re: Μεταθέσεις και διαφορές

Re: Μεταθέσεις και διαφορές

Μέλη σε σύνδεση