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

Σεπτεμβρίου 14, 2009

Απαγορευμένοι πίνακες

Έστω A ένας n\times n πίνακας από \heartsuit και \clubsuit. Υποθέτουμε ότι ο A δεν περιέχει κανένα 2\times 2 υποπίνακα που αποτελείται μόνο από \heartsuit. Βρείτε ένα άνω φράγμα για τον συνολικό αριθμό των \heartsuit.

Advertisements

27 Σχόλια »

  1. Έστω n άρτιος.Τότε, ένας nxn πίνακας θα έχει ((n)^2)/4 ξένους 2×2 υποπίνακες.Στη περίπτωση που βάζουμε τις περισσότερες δυνατές καρδιές χωρίς να έχουμε 2×2 υποπίνακα που να αποτελείται μόνο από αυτές, θα έχουμε 3 καρδιές σε κάθε υποπίνακα, δηλαδή συνολικά (3/4)(n)^2 καρδιές.

    Έστω n περιττός.Τότε, βγάζοντας την τελευταία γραμμή και στήλη, αναγόμαστε στην προηγούμενη περίπτωση με n-1, και γεμίζοντας με καρδιές την τελευταία γραμμή-στήλη, καταλήγουμε στο (3/4)(n-1)^2 + 2n.

    Μου αρέσει!

    Σχόλιο από olack — Σεπτεμβρίου 14, 2009 @ 9:44 μμ

  2. Συγνώμη, στην περιττή περίπτωση, είναι (3/4)(n-1)^2+2n-1.

    Μου αρέσει!

    Σχόλιο από olack — Σεπτεμβρίου 14, 2009 @ 9:48 μμ

  3. Συγνώμη, δεν εξήγησα τι ακριβώς εννοώ λέγοντας «υποπίνακας». Εννοώ ότι δεν υπάρχουν i,j,k,l έτσι ώστε a_{ij}=a_{ik}=a_{lj}=a_{lk}=\heartsuit, και όχι ότι δεν υπάρχουν i,j έτσι ώστε a_{ij}=a_{i+1j}=a_{ij+1}=a_{i+1j+1}=\heartsuit, όπως υποθέτεις.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 15, 2009 @ 11:05 πμ

  4. 4. Από τη στιγμή που ψάχνουμε να βρούμε ένα άνω φράγμα για το συνολικό αριθμό των καρδιών, σημαίνει ότι ψάχνουμε
    την περίπτωση όπου ο αριθμός των σπαθιών είναι ο ελάχιστος δυνατός προκειμένου να ισχύει η συνθήκη του προβλήματος.
    Ο ελάχιστος αριθμός σπαθιών που μπορούν να τοποθετηθούν σε έναν τέτοιο πίνακα n X n είναι div(n/2), όπου div το
    ακέραιο πηλίκο. Επομένως ο αριθμός των καρδιών θα έιναι n^2 – (div(n/2))^2. Υπάρχουν μόνο 2 πίνακες n X n που έχουν
    τον ίδιο ελάχιστο δυνατό αριθμό σπαθιών. Ο ένας έχει n άρτιο και ο άλλος έχει n περιττό. Όταν το n είναι περιττό
    τότε έχουμε περισσότερες καρδιές για τον ίδιο αριθμό σπαθιών. Δηλαδή :

    Πίνακας 4Χ4 έχει minimum 4 σπαθιά όπως και ο πίνακας 5Χ5, αλλά ο 5Χ5 έχει περισσότερες καρδιές.
    Ομοίως ισχύει και για τους πίνακες 6Χ6 και 7Χ7 (έχουν 9 σπαθιά) όπως και για τους 8Χ8 και 9Χ9
    (έχουν 16 σπαθιά) κοκ…

    Μου αρέσει!

    Σχόλιο από aaennarion — Σεπτεμβρίου 22, 2009 @ 4:01 πμ

  5. Ούπς! Τυπογραφικό λάθος… Στη τρίτη σειρά γράφω «Ο ελάχιστος αριθμός σπαθιών που μπορούν να τοποθετηθούν σε έναν
    τέτοιο πίνακα n X n είναι div(n/2)». Ηθελα να πω «Ο ελάχιστος αριθμός σπαθιών που μπορούν να τοποθετηθούν σε έναν
    τέτοιο πίνακα n X n είναι (div(n/2))^2».

    Μου αρέσει!

    Σχόλιο από aaennarion — Σεπτεμβρίου 22, 2009 @ 4:28 πμ

  6. Όσο αναφορά το γιατί ο ελάχιστος αριθμός σπαθιών στον συγκεκριμένο πίνακα n X n είναι ίσος με (div(n/2))^2. Παραθέτω το παρακάτω παράδειγμα.
    Αν ο πίνακας ήταν 2 Χ 2, τότε η διάταξη αν υποθέσουμε πως 0 είναι κούπα και 1 το σπαθί, θα ήταν κάπως έτσι : 0 0
    0 1

    Στην περίπτωση του 3 Χ 3 αρκεί να προσθέσουμε μία στήλη με 0 στο τέλος και μία γραμμή με μηδενικά από κάτω, δηλαδη : 0 0 0
    0 1 0
    0 0 0
    Όπου επιτυγχάνουμε την τέλεια επικάλυψη (ίδιος αριθμός σπαθιών με πριν).
    Όταν το n είναι άρτιο για κάθε 1 αντιστοιχούν 3 0 σε διάταξη Γ, περίπτωση 4 Χ 4 : 0 0 0 0
    0 1 0 1
    0 0 0 0
    0 1 0 1
    Δεν μπορούν να υπάρχουν λιγότερα σπαθιά γιατι ουσιαστικά ένας πίνακας 4 Χ 4
    είναι 4 πίνακες 2 Χ 2. Στην περίπτωση του 5 Χ 5, προσθέτουμε γραμμή και στήλη όπως προηγουμένως και έχουμε : 0 0 0 0 0
    0 1 0 1 0
    0 0 0 0 0
    0 1 0 1 0
    0 0 0 0 0
    Όπου πάλι επιτυγχάνουμε την τέλεια επικάλυψη (ίδιος αριθμός σπαθιών με πριν).
    Αντιστοίχως και για 6 Χ 6, όπου είναι 9 πίνακες 2 Χ 2, και έχει τον ίδιο αριθμό σπαθιών με τον πίνακα 7 Χ 7 κοκ.

    Sorry για το πολλαπλό post αλλά είναι η πρώτη φορά που προσπαθώ να δώσω λύση στο συγκεκριμένο site.
    Ελπίζω να είναι και σωστή. Cheers!

    Μου αρέσει!

    Σχόλιο από aaennarion — Σεπτεμβρίου 22, 2009 @ 5:06 πμ

  7. Νομίζω παρανόησες και εσύ το «2\times2 υποπίνακας». Εννοούμε οποιαδήποτε ορθογώνια διάταξη από 4 καρδιές.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 22, 2009 @ 9:35 μμ

  8. Μια παρατήρηση πάνω στις απαντήσεις των olack και aaennarion η οποία ίσως βοηθήσει.
    Και οι δύο έχουν τάξη μεγέθους n^2. Αυτό ασυμπτωτικά δεν είναι καθόλου ικανοποιητικό, αφού ο ίδιος ο πίνακας αποτελείται από n^2 στοιχεία. Αυτό που πρέπει να προσπαθήσετε να κάνετε είναι να βελτιώσετε τον εκθέτη 2.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 22, 2009 @ 11:50 μμ

  9. Εχοντας στο μυαλο μας την εξης περιπτωση 5×5 πινακα:
    11111
    10000
    10000
    10000
    10000
    οπου οι ασσοι ειναι οι καρδιες, μπορουμε να υποπτευθουμε οτι ενα ανω φραγμα ειναι το πολυ 2n-1 γιατι οπου και να προσθεσουμε
    εναν ασσο στο παραπανω πινακα θα παρουμε εναν 2×2 υποπινακα μονο με ασσους.

    Με επαγωγη μπορουμε να δειξουμε το εξης: Καθε nxn πινακας, n>1, μπορει να εχει 2n-1 καρδιες χωρις να περιεχει κανενα 2×2 υποπινακα
    μονο με καρδιες. Για n=2 ειναι προφανες. Εστω οτι ενας (n-1)x(n-1) πινακας μπορει να εχει 2n-3 καρδιες χωρις να περιεχει κανενα
    2×2 υποπινακα μονο με καρδιες τοτε ο nxn πινακας
    1xx….x
    0xx….x
    0xx….x
    ……..
    0xx….x
    10000000
    εχει 2n-1 καρδιες χωρις να περιεχει κανενα 2×2 υποπινακα μονο με καρδιες. Αρα το ανω φραγμα των απαγορευμενων πινακων ειναι 2n-1.

    Μου αρέσει!

    Σχόλιο από yannispantazis — Σεπτεμβρίου 23, 2009 @ 4:24 μμ

  10. @yannispantazis:
    ο πίνακας
    1 1 0
    0 1 1
    1 0 1
    δεν έχει 2×2 υποπίνακα μόνο με άσσους αλλά περιέχει περισσότερους από 2n-1 άσσους.

    Μου αρέσει!

    Σχόλιο από stedes — Σεπτεμβρίου 23, 2009 @ 7:47 μμ

  11. Όπως παρατηρεί ο stedes, η εικασία τού yannispantazis δεν είναι σωστή. Ένα άλλο παράδειγμα είναι ο 5\times 5 πίνακας

    \left[\begin{matrix}1&0&0&1&1\\ 0&0&0&1&0\\ 0&1&1&1&0\\ 0&1&0&0&0\\ 1&1&0&0&0\end{matrix}\right]

    ο οποίος έχει 10 καρδιές (μπορεί να χειροτερέψει πολύ αν μεγαλώσει η διάσταση). Πέρα όμως από αυτό, δεν είναι σωστή η επαγωγή. Η επαγωγική υπόθεση θα έπρεπε να είναι «έχει το πολύ xyz καρδιές» όχι «μπορει να έχει xyz καρδιές». Τότε όμως δεν δουλεύει το επαγωγικό βήμα.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 23, 2009 @ 8:06 μμ

  12. Έστω A ένας πίνακας που δεν περιέχει 2\times 2 υποπίνακες μόνο με καρδιές. Έστω επίσης x_i το πλήθος τον καρδιών στην i στήλη του πίνακα και x το συνολικό πλήθος των καρδιών σε όλο τον πίνακα.
    Αν k,l είναι δύο αριθμοί ώστε στην i γραμμή τα στοιχεία a_{i,k},a_{i,l} να είναι και τα δύο καρδιές, τότε για κανένα j\neq i τα a_{j,k},a_{j,l} δεν είναι και τα δυο καρδιές. Αυτό σημαίνει ότι σε κάθε γραμμή του πίνακα αντιστοιχούν κάποια ζεύγη (k,l), καθένα από τα οποία αντιστοιχεί σε μία και μόνο γραμμή.
    Στην i γραμμή το πλήθος των ζευγών από καρδιές είναι \binom{x_i}{2}, άρα το συνολικό πλήθος τέτοιων ζευγών στον πίνακα είναι \sum_{i=1}^n\binom{x_i}{2}.
    Επίσης όλες οι δυνατές τιμές που μπορούν να πάρουν τα ζεύγη (k,l) είναι \binom{n}{2} ,άρα ισχύει
    \sum_{i=1}^n\binom{x_i}{2}\le\binom{n}{2}.
    Μετά από πράξεις στο παραπάνω καταλήγουμε στην ανισότητα
    \sum_{i=1}^n{x_i^2}\le 2\binom{n}{2}+\sum_{i=1}^n{x_i}=2\binom{n}{2}+x.

    Όμως ισχύει και ότι \sum_{i=1}^n{x_i^2}\ge\frac{(\sum_{i=1}^n{x_i})^2}{n}=\frac{x^2}{n}.

    Άρα προκύπτει ότι \frac{x^2}{n}\le 2\binom{n}{2}+x, από την οποία βρίσκουμε ότι x\le \frac{n(1+\sqrt{4n-3})}{2} και επειδή το x είναι ακέραιος τελικά ισχύει
    x\le \lfloor{\frac{n(1+\sqrt{4n-3})}{2}\rfloor}, το οποίο είναι ένα άνω φράγμα για το συνολικό αριθμό των καρδιών.

    Μου αρέσει!

    Σχόλιο από stedes — Σεπτεμβρίου 24, 2009 @ 4:03 μμ

  13. Σωστά.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 24, 2009 @ 4:41 μμ

  14. Ένα ερώτημα που προκύπτει είναι αν μπορούμε να βρούμε τον ακριβή τύπο που δίνει το μέγιστο πλήθος καρδιών για κάθε n.
    Παρατήρησα ότι αν ο n είναι της μορφής k^2-k+1 για κάποιο φυσικό k, τότε το μέγιστο πλήθος καρδιών είναι k(k^2-k+1) που ισούται με το άνω φράγμα παραπάνω.
    Αν όμως ο n είναι της μορφής k^2-k+2 τότε το μέγιστο πλήθος καρδιών είναι (k+1)(k^2-2k+3) που δεν ισούται πάντα με το άνω φράγμα.
    Συγκεκριμένα οι πρώτοι όροι της ακολουθίας του μέγιστου αριθμού από καρδιές είναι
    1,3,6,9,12,16,21,24,29,34,39,45,52,55,… (A072567).

    p.s. Στο προηγούμενο μήνυμα εκεί που γράφω «x_i το πλήθος τον καρδιών στην i στήλη» το σωστό είναι «x_i το πλήθος των καρδιών στην i γραμμή».

    Μου αρέσει!

    Σχόλιο από stedes — Σεπτεμβρίου 25, 2009 @ 1:57 πμ

  15. Δεν νομίζω ότι είναι δυνατό να βρει κανείς «ακριβή τύπο». Σε τέτοιου είδους προβλήματα αυτό που μας ενδιαφέρει είναι η τάξη μεγέθους.
    Η τάξη μεγέθους που βρήκες (n^{3/2}) είναι η καλύτερη δυνατή.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 25, 2009 @ 2:23 πμ

  16. Toο easy:

    Αν ν είναι άρτιος: άνω φράγμα = 3(ν^2)/4

    Αν ν είναι περιττός: άνω φράγμα = 3(ν-1)^2/4 + 2ν-1

    Τσεκάρετε με ν = 1, 2, 3, 4,…

    Το κόλπο είναι να διατάξουμε τα στοιχεία σε Γ , ΓΓ , ΓΓΓ ,… (λίγο φαντασία…)
    ΓΓ ΓΓΓ
    ΓΓΓ

    Παρατηρήστε οτι σε κάθε [Γ] έχουμε 3 καρδιές και ένα τριφύλλι.

    Anything harder?

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 7:15 μμ

  17. Επειδή στο προηγούμενο σχόλιο δεν έγινε ακριβής μεταφορά αυτού που έγραψα, θα προσπαθήσω να το καταστίσω σαφές με τις ακόλουθες κατασκευές (1 = κούπα)

    [1] , [{1,1},{1,0}], [{1,1,1},{1,0,1},{1,1,1}], [{1,1,1,1},{1,0,1,0},{1,1,1,1},{1,0,1,0}], …..

    όπου {.,…} συμβολίζει γραμμή μήτρας (Mathematica). Παρατηρήστε τα ‘Γ’ που σχηματίζονται με τα 1 (κούπες) στις περιπτώσεις 2×2, 4×4, 6×6, κοκ. cool?

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 7:24 μμ

  18. Όπως ανέφερα και σε προηγούμενο σχόλιο, σε ένα τέτοιου είδους πρόβλημα, το n^2 δεν είναι λέει, ασυμπτωτικά, πολλά πράγματα.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 25, 2009 @ 7:37 μμ

  19. Στο σχόλιο #16 (αρχή) αναφέρω επακριβώς το άνω φράγμα… just check it

    Στο σχόλιο #14 οι πρώτοι όροι 1,3,6,9,12,16,21 νομίζω είναι σωστοί, όχι όμως οι υπόλοιποι. check

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 7:55 μμ

  20. Τώρα βλέπω οτι ήδη ο olac απο το σχόλιο 2 έχει τη λύση στο πρόβλημα… Αλλά, από ότι είδα όταν γράφετε 2×2 υποπίνακας δεν εννοείται 2×2 πίνακας εντός του νxν πινακα?!!! Γιατί δεν καταστήσατε αυτό σαφές απο την αρχή? Δηλ. το σχόλιο 7 είναι λίγο … καθυστερημένο…. Όταν λέμε 2×2 εννούμε 2×2 και όχι 1×4……!!!……..

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 9:04 μμ

  21. Αλλά ακόμα και σε αυτή την περίπτωση, το άνω όριο μπορεί να βρεθεί απο μήτρες που περιέχουν, στα μονά ζεύγη γραμμών, Γ L διαδοχικά, και στα ζυγά ζεύγη γραμμών «ανάποδο Γ» «ανάποδο L» διαδοχικά, όπου

    Γ=[{1,1},{1,0}]
    L=[{1,0},{1,1}]
    ανάποδο Γ=[{1,1},{0,1}]
    ανάποδο L=[{0,1},{1,1}]

    Το άνω φράγμα δεν το υπολόγισα αλλά εξάγεται εύκολα. Πάλι πρέπει να διακρίνει κάποιος στις περιπτώσεις του άρτιου/περιττού αριθμού γραμμών (ν).

    P.S. Όταν γράφετε nxn μήτρα εννοείτε nxn μήτρα και όχι κάποια άλλη ορθογώνια διάταξη. Σωστά;

    Μου αρέσει!

    Σχόλιο από harris1976 — Σεπτεμβρίου 25, 2009 @ 9:20 μμ

  22. Το τι εννοώ με 2×2 υποπίνακα το ξεκαθάρισα με απόλυτο φορμαλισμό στο σχόλιο 3.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 26, 2009 @ 8:49 μμ

  23. Ακριβής τύπος μάλλον είναι εξαιρετικά απίθανο να βρεθεί. Υπάρχει όμως το ερώτημα αν το 3/2 είναι το καλύτερο δυνατό ή αν μπορεί να μειωθεί και άλλο.

    Σε αυτή την περίπτωση το 3/2 είναι πράγματι το καλύτερο δυνατό. Μάλιστα, η απάντηση του stedes στο σχόλιο 12 είναι σωστή για άπειρες τιμές του ν. Μπορείτε να το δείξετε;

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Σεπτεμβρίου 28, 2009 @ 5:39 μμ

  24. Ο Δημήτρης εννοεί το εξής:
    Ο stedes απέδειξε ένα άνω φράγμα τής μορφής Cn^{3/2}. Εσείς τώρα, για άπειρα n, βρείτε έναν n\times n πίνακα με την ιδιότητα που τόσο σας μπέρδεψε, ο οποίος να έχει τουλάχιστον n^{3/2} καρδιές. Αυτό θα δείξει ότι στο φράγμα τού stedes ο εκθέτης δεν μπορεί να βελτιωθεί.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 28, 2009 @ 6:55 μμ

  25. Ενα πιο γενικο σχολιο:

    Αυτο το προβλημα ειναι μεταμφιεσμενα προβλημα θεωριας γραφηματων. Δοσμενου ενος n x n πινακα οριζουμε ενα γραφημα με n κορυφες ως εξης: οι κορυφες i και j συνδεονται με ακμη αν-ν το ij στοιχειο του πινακα ειναι καρδια. Τοτε το προβλημα ρωτα για ανω φραγμα στο πληθος των ακμων δεδομενου οτι το γραφημα δεν εχει πληρη υπογραφηματα ταξης 4 (4-complete subgraphs).

    Μου αρέσει!

    Σχόλιο από partalopoulo — Σεπτεμβρίου 30, 2009 @ 8:17 πμ

  26. Επειδή ο πίνακας δεν είναι συμμετρικός (μπορεί να έχουμε καρδία στο ij αλλά σπαθί στο ji) το αντίστοιχο πρόβλημα θεωρίας γραφημάτων είναι το εξής:

    Να βρεθεί ο μέγιστος αριθμός ακμών ενός διμερούς γραφήματος με ν στοιχεία στο κάθε μέρος δεδομένου ότι το γράφημα δεν έχει κύκλο μήκους τέσσερα (δηλαδή τέσσερις κορυφές a,b,c,d ώστε οι ab,bc,cd και da να είναι ακμές).

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Σεπτεμβρίου 30, 2009 @ 1:01 μμ

  27. Οντως, αγνοησα την περιπτωση που ο πινακας δεν ειναι συμμετρικος (η οποια συμβαιναι και με…πιθανοτητα 1 οταν n\to\infty!) Ευχαριστω για τη διορθωση.

    Μου αρέσει!

    Σχόλιο από partalopoulo — Σεπτεμβρίου 30, 2009 @ 4:23 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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