Mια συνδυαστική!

ksofsa · #1

Προσδιορίστε αν είναι δυνατό να διατάξουμε τους αριθμούς 1,1,2,2,...,n,n

έτσι ώστε να υπάρχουν

αριθμοί μεταξύ δύο $j's,1\leq j\leq n$ , όταν n=2000,n=2001,n=2002.

(Για παράδειγμα, για n=4

,

είναι μια τέτοια διάταξη.)

ksofsa · #2

ΕΠΑΝΑΦΟΡΑ

#3

Θα δείξουμε ότι γίνεται για n=2000

αλλά όχι για n=2001,2002

Έστω ότι γίνεται για κάποιο

. Για κάθε αριθμό

, έστω

οι θέσεις που εμφανίζεται με x_k < y_k

. Τότε είναι

$\displaystyle \sum_{k=1}^n (x_k+y_k) = 1+2+\cdots + 2n = \frac{2n(2n+1)}{2}$

και

$\displaystyle \sum_{k=1}^n (y_k-x_k) = 2+3+\cdots + (n+1) = \frac{n(n+3)}{2}-1$

Άρα

$\displaystyle 2\sum_{k=1}^n y_k = \frac{4n^2 + 2n - n^2-3n}{2} = \frac{3n^2-n}{2}$

Πρέπει λοιπόν 4|3n^2 - n

. Για $n\equiv 1 \bmod 4$ και $n \equiv 2 \bmod 4$ εύκολα ελέγχουμε ότι αυτό είναι αδύνατο.

Άρα για n=2001,2002

δεν γίνεται. Για n=2000

δεν σημαίνει απαραίτητα ότι γίνεται. Πρέπει να δώσουμε κατασκευή. Δίνουμε μια κατασκευή η οποία δουλεύει για n=4m

.

Έστω $A = \{1,3,\ldots,2m-3}, B = \{2,4,\ldots,2m-2\}, C = \{2m,2m+2,\ldots,4m-4\}$ και $D = \{2m+1,2m+3,\ldots,4m-3\}$ . Τα A,B,C,D

είναι ξένα μεταξύ τους με m-1

στοιχεία το κάθε ένα.

Θα γράψω

για να δηλώνω ότι έγραψα τα στοιχεία του συνόλου

με αύξουσα σειρά και

αν τα γράψω με φθίνουσα σειρά. Παρατηρώ ότι αν μεταξύ του

και

έχω ένα στοιχείο τότε όλα τα στοιχεία του

έχουν τη ζητούμενη ιδιότητα. Ομοίως μεταξύ του

και

θέλω δύο στοιχεία, μεταξύ του

και

θέλω

στοιχεία και μεταξύ του

και

θέλω

στοιχεία.

Γράφω τώρα τους αριθμούς με την εξής σειρά:

C',4m-2,A',4m-1,A,C,4m,D',4m-2,B',2m-1,4m-1,B,D,2m-1,4m

Εύκολα τώρα ελέγχεται ότι η συγκεκριμένη διάταξη έχει τη ζητούμενη ιδιότητα.

Mια συνδυαστική!

Mια συνδυαστική!

Re: Mια συνδυαστική!

Re: Mια συνδυαστική!

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