Προβλήματα Μαθηματικών

Οκτώβριος 13, 2011

Αδιασταύρωτες διαμερίσεις

Filed under: Άλυτα Προβλήματα — Michalis Loulakis @ 2:32 μμ

Ας είναι X_n=\{1,2,3,\ldots,n\}. Θα ονομάζουμε μια διαμέρισή του διασταυρωμένη αν υπάρχουν x,y,z,w με 1\le x<y<z<w\le n και  τα x,z ανήκουν στο ίδιο διαμερίζον σύνολο ενώ τα y,w ανήκουν και τα δύο σε κάποιο άλλο διαμερίζον σύνολο. Π.χ. η X_5=\{1,3,4\}\cup\{2,5\} είναι μια διασταυρωμένη διαμέριση του X_5. Τις διαμερίσεις που δεν είναι διασταυρωμένες θα τις ονομάζουμε αδιασταύρωτες.

Πόσες αδιασταύρωτες διαμερίσεις έχει το X_n;

Advertisements

3 Σχόλια »

  1. Tha einai (n-1)+(n-2)+…+(n-[n/2]+1),opou [] to akeraio meros.(O typos aytos DEN metraei tis diameriseis stis opoies ena apo ta dyo synola exei plitharithmo 1.An theloume na metrisoume kai aytes prosthetoume n)

    Tha leme oti ena synolo S={A1,A2,…,An} opou Ai anikoun stous fysikous,einai (*) an DEN yparxei A’ stous fysikous tetoios oste Ai<A'<Ai+1 ,i={1,2,…,n}.

    Esto oti theloume na vroume tis adiastayrotes diameriseis tou X6.Merikes apo aytes tha nai
    {1,2}U{3,4,5,6} , {2,3}U{1,4,5,6} , {1,2,3}U{4,5,6} klp.
    Paratiroume diladi oti se kathe periptosi ena apo ta dyo synola einai (*).Kai ayto einai logiko kathoti an mia diamerisi einai diastayromeni mporoume na vroume gnisios ayxousa akolouthia 4 arithmon k1,k2,k3,k4 me k1,k3 na anikoun sto proto synolo kai kai k2,k4 na anoikoun sto allo.

    Diladi an theloume na vroume A,B synola me Xn=AUB kai A,B na min diastayronontai prepei na metrisoume tis parakato diameriseis.

    {1,2}U{3,4,…,n}
    {2,3}U{1,4,…,n}
    .
    .
    {n-1,n}U{1,2,…,n-2} kai meta

    {1,2,3}U{3,4,…,n}
    {2,3,4}U{1,5,…,n}
    .
    .
    {n-2,n-1,n}U{1,2,….,n-3}

    Xekiname diladi me oles tis diameriseis AUB,A synolo (*) me |A|=2,meta me |A|=3 mexri |A|=[n/2] (diladi an eimaste px sto X7 tha metrisoume mexri kai gia |A|=3 kathoti an pame gia |A|=4 to |B|=3 ara tha xanametrame mia diamerisi pou exoume idi katagrapsei).

    Ara telika to plithos ton zitoumenon diameriseon tha einai #{diameriseis AUB me |A|=2}+#{diameriseis AUB me |A=3|}+…+{diameriseis AUB me |A=[n/2]|} opou panta A einai (*).

    eykola vlepoume oti #{diameriseis AUB me |A=m|}=n-m+1.Ara pernontas diadoxika m=2,3,…,[n/2] exo oti to zitoumeno tha nai (n-1)+(n-2)+…+(n-[n/2]+1).

    Μου αρέσει!

    Σχόλιο από zizizzzzz — Νοέμβριος 21, 2011 @ 4:36 πμ

  2. prostheto,

    «Paratiroume diladi oti se kathe periptosi ena apo ta dyo synola einai (*).Kai ayto einai logiko kathoti an mia diamerisi einai diastayromeni mporoume na vroume gnisios ayxousa akolouthia 4 arithmon k1,k2,k3,k4 me k1,k3 na anikoun sto proto synolo kai kai k2,k4 na anoikoun sto allo»

    Ara an to ena synolo A einai (*) den tha mporoume na vroume tetoia akolouthia kathoti an k1,k3 anikoun sto A den tha yparxei fysikos k me k1<k<k3 (logo (*)) ara den tha yparxoun kai ta k2,k4.Omoios an ta k2,k4 anikoun sto A .

    Μου αρέσει!

    Σχόλιο από zizizzzzz — Νοέμβριος 21, 2011 @ 4:46 πμ

  3. Μπορούμε όμως να έχουμε διαμερίσεις σε περισσότερα από δύο υποσύνολα, Π.χ. \{1,5,6\}\cup\{2,4\}\cup\{3\}.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 23, 2011 @ 2:35 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: