Πίνακας με 1 και 0

Γ.-Σ. Σμυρλής · #1

Έστω ότι ο $A=(a_{ij})$ είναι ένας $m\times n$ πίνακας, με m<n

, του οποίου όλα τα στοιχεία είναι 0 ή 1, και σε κάθε στήλη του υπάρχει τουλάχιστον ένα στοιχείο το οποίο ισούται με 1. Δείξατε ότι υπάρχει κάποιο στοιχείο του πίνακα το οποίο ισούται με 1, και στην γραμμή αυτού του στοιχείου υπάρχουν περισσότερα στοιχεία τα οποία ισούνται με 1 απ΄ότι στην στήλη του ιδίου στοιχείου. Δηλαδή υπάρχει ${\color{red}(i_0,j_0)}\in\{1,\ldots,m\}\times\{1,\ldots,n\}$ , ώστε

$\displaystyle{\color{red} \sum_{i}a_{ij_0} < \sum_{j}a_{i_0j}. }$

#2

Γ.-Σ. Σμυρλής έγραψε:Έστω ότι ο $A=(a_{ij})$ είναι ένας $m\times n$ πίνακας, με , του οποίου όλα τα στοιχεία είναι 0 ή 1, και σε κάθε στήλη του υπάρχει τουλάχιστον ένα στοιχείο το οποίο ισούται με 1. Δείξατε ότι υπάρχει κάποιο στοιχείο του πίνακα το οποίο ισούται με 1, και στην γραμμή αυτού του στοιχείου υπάρχουν περισσότερα στοιχεία τα οποία ισούνται με 1 απ΄ότι στην στήλη του ιδίου στοιχείου. Δηλαδή υπάρχει $(i,j)\in\{1,\ldots,m\}\times\{1,\ldots,n\}$ , ώστε

$\displaystyle{ \sum_{i}a_{ij} < \sum_{j}a_{ij}. }$

Ας υποθέσουμε, με απαγωγή σε άτοπο, ότι

$\displaystyle{ \sum_{i}a_{ij} \geq \sum_{j}a_{ij}}$

για κάθε $(i,j)\in\{1,\ldots,m\}\times\{1,\ldots,n\}$ .

Από υπόθεση τα παραπάνω αθροίσματα είναι

. Συνεπώς,

$\dfrac{a_{ij}}{\sum_{j}a_{ij}}\geq \dfrac{a_{ij}}{\sum_{i}a_{ij}}$ για κάθε $(i,j)\in\{1,\ldots,m\}\times\{1,\ldots,n\}$

Αθροίζοντας για όλα τα ζεύγη (i,j)

παίρνουμε

$m=\displaystyle{\sum_{i,j}\dfrac{a_{ij}}{\sum_{j}a_{ij}}\geq \sum_{i,j}\dfrac{a_{ij}}{\sum_{i}a_{ij}}}=n$ ,

άτοπο.

Σχόλιο: Για περισσότερα πάνω σε πίνακες με στοιχεία 0 και 1 δείτε, π.χ. http://yufeizhao.com/olympiad/doublecounting_mop.pdf

Φιλικά,

Αχιλλέας

Γ.-Σ. Σμυρλής · #3

achilleas έγραψε:
Ας υποθέσουμε, με απαγωγή σε άτοπο, ότι

$\displaystyle{ \sum_{i}a_{ij} \geq \sum_{j}a_{ij}}$

για κάθε $(i,j)\in\{1,\ldots,m\}\times\{1,\ldots,n\}$ .

Από υπόθεση τα παραπάνω αθροίσματα είναι .

Δυστυχώς δεν υπάρχει τέτοια υπόθεση, για κάθε (i,j)

!

#4

Γ.-Σ. Σμυρλής έγραψε:
achilleas έγραψε:
Ας υποθέσουμε, με απαγωγή σε άτοπο, ότι

$\displaystyle{ \sum_{i}a_{ij} \geq \sum_{j}a_{ij}}$

για κάθε $(i,j)\in\{1,\ldots,m\}\times\{1,\ldots,n\}$ .

Από υπόθεση τα παραπάνω αθροίσματα είναι .
Δυστυχώς δεν υπάρχει τέτοια υπόθεση, για κάθε !

Oops! Δεν το έγραψα σωστά: Αν $\displaystyle{ \sum_{i}a_{ij} \geq \sum_{j}a_{ij}}$ όποτε $a_{ij}=1$ , τότε (η συνέχεια ίδια) έπεται ότι
$m\geq n$ .

Φιλικά,

Αχιλλέας

#5

Δουλεύουμε με επαγωγή στον αριθμό των άσσων. Θα δείξουμε δηλαδή ότι για κάθε

αν υπάρχει $m \times n$ πίνακας με ακριβώς

άσσους που ικανοποιεί τις συνθήκες τότε ικανοποιεί και το συμπέρασμα.

Ο πίνακας πρέπει να έχει τουλάχιστον δυο άσσους και έχει δύο μόνο αν m=1,n=2

. Σε αυτήν την περίπτωση το συμπέρασμα είναι προφανές.

Περίπτωση πρώτη: Μπορούμε να βρούμε

άσους ώστε κάθε γραμμή να εχει ακριβώς 1 άσσο και κάθε στήλη να έχει το πολύ ένα άσσο. Σβήνουμε τότε αυτούς τους άσους. Σβήνουμε επίσης όσες γραμμές και στήλες δεν έχουν πλέον άσσους. Έστω ότι σβήσαμε $\ell$ στήλες. Σε κάθε στήλη που σβήσαμε, αν η αντίστοιχη γραμμή (αυτή που περιείχε τον κοινό άσσο) είχε τουλάχιστον δύο άσσους τότε τελειώσαμε. Αν όχι τότε αυτό σημαίνει πως σβήνουμε τουλάχιστον $\ell$ γραμμές. Τότε όμως ο πίνακας που παίρνουμε ικανοποιεί τις συνθήκες και από την επαγωγική υπόθεση έχει ένα άσσο ώστε η γραμμή του έχει περισσότερους άσσους από την στήλη του. Το ίδιο όμως πρέπει να ισχύει και για τον αρχικό πίνακα αφού η γραμμή αυτού του στοιχείου θα έχει ένα επιπλέον άσσο ενώ η στήλη του θα έχει το πολύ ένα άσσο.

Περίπτωση δεύτερη: Αν δεν ισχύει η πρώτη περίπτωση τότε από το θεώρημα του γάμου μπορούμε να βρούμε

γραμμές ώστε όλοι οι άσσοι τους να περιέχονται το πολύ σε s-1

στήλες. (Πρέπει $s \geqslant 2$ αφού κάθε γραμμή έχει τουλάχιστον ένα άσσο.) Σβήνουμε αυτές τις γραμμές και όλες τις στήλες στις οποίες αυτές οι γραμμές έχουν άσσους. Ο πίνακας που μένει ικανοποιεί τις συνθήκες οπότε από την επαγωγική υπόθεση υπάρχει ένας άσσος ώστε η γραμμή του έχει περισσότερους άσσους από την στήλη του. Το ίδιο όμως πρέπει να ισχύει και για τον αρχικό πίνακα αφού η στήλη αυτού του στοιχείου δεν μπορεί να έχει επιπλέον άσσους.

Γ.-Σ. Σμυρλής · #6

Demetres έγραψε:Δουλεύουμε με επαγωγή στον αριθμό των άσσων. Θα δείξουμε δηλαδή ότι για κάθε αν υπάρχει $m \times n$ πίνακας με ακριβώς άσσους που ικανοποιεί τις συνθήκες τότε ικανοποιεί και το συμπέρασμα.

Ο πίνακας πρέπει να έχει τουλάχιστον δυο άσσους και έχει δύο μόνο αν . Σε αυτήν την περίπτωση το συμπέρασμα είναι προφανές.

Περίπτωση πρώτη: Μπορούμε να βρούμε άσους ώστε κάθε γραμμή να εχει ακριβώς 1 άσσο και κάθε στήλη να έχει το πολύ ένα άσσο. Σβήνουμε τότε αυτούς τους άσους. Σβήνουμε επίσης όσες γραμμές και στήλες δεν έχουν πλέον άσσους. Έστω ότι σβήσαμε $\ell$ στήλες. Σε κάθε στήλη που σβήσαμε, αν η αντίστοιχη γραμμή (αυτή που περιείχε τον κοινό άσσο) είχε τουλάχιστον δύο άσσους τότε τελειώσαμε. Αν όχι τότε αυτό σημαίνει πως σβήνουμε τουλάχιστον $\ell$ γραμμές. Τότε όμως ο πίνακας που παίρνουμε ικανοποιεί τις συνθήκες και από την επαγωγική υπόθεση έχει ένα άσσο ώστε η γραμμή του έχει περισσότερους άσσους από την στήλη του. Το ίδιο όμως πρέπει να ισχύει και για τον αρχικό πίνακα αφού η γραμμή αυτού του στοιχείου θα έχει ένα επιπλέον άσσο ενώ η στήλη του θα έχει το πολύ ένα άσσο.

Περίπτωση δεύτερη: Αν δεν ισχύει η πρώτη περίπτωση τότε από το θεώρημα του γάμου μπορούμε να βρούμε γραμμές ώστε όλοι οι άσσοι τους να περιέχονται το πολύ σε στήλες. (Πρέπει $s \geqslant 2$ αφού κάθε γραμμή έχει τουλάχιστον ένα άσσο.) Σβήνουμε αυτές τις γραμμές και όλες τις στήλες στις οποίες αυτές οι γραμμές έχουν άσσους. Ο πίνακας που μένει ικανοποιεί τις συνθήκες οπότε από την επαγωγική υπόθεση υπάρχει ένας άσσος ώστε η γραμμή του έχει περισσότερους άσσους από την στήλη του. Το ίδιο όμως πρέπει να ισχύει και για τον αρχικό πίνακα αφού η στήλη αυτού του στοιχείου δεν μπορεί να έχει επιπλέον άσσους.

Η "Πρώτη Περίπτωση" δεν μπορεί ποτέ να ισχύει καθώς, αν υπήρχαν

άσοι, ώστε κάθε γραμμή να είχε ακριβώς 1 άσο, αφού όλες οι γραμμές είναι

, τότε θα είχαμε ακριβώς

άσους. Άτοπο.

Στην "Δεύτερη Περίπτωση" τί ακριβώς λέει το Θεώρημα του Γάμου;

Γ.-Σ. Σμυρλής · #7

Συγγνώμη, αλλά εκανα κάποιο λάθος στην διατύπωση το οποίο εδιόρθωσα με κόκκινο χρώμα.

Αυτό ίσως μπέρδεψε τον achilleas, αφού τα αθροίσματα

$m=\displaystyle{\sum_{i,j}\dfrac{a_{ij}}{\sum_{j}a_{ij}}\geq \sum_{i,j}\dfrac{a_{ij}}{\sum_{i}a_{ij}}}=n$ ,

δεν ορίζονται απαραίτητα, δοθέντος ότι οι παρονομαστές ενδέχεται να μηδενίζονται.

#8

Γ.-Σ. Σμυρλής έγραψε: Η "Πρώτη Περίπτωση" δεν μπορεί ποτέ να ισχύει καθώς, αν υπήρχαν άσοι, ώστε κάθε γραμμή να είχε ακριβώς 1 άσο, αφού όλες οι γραμμές είναι , τότε θα είχαμε ακριβώς άσους. Άτοπο.

Δεν μιλάω για

γραμμές με ακριβώς ένα άσσο στην κάθε μια αλλά για

άσσους ώστε κάθε ένας να βρίσκεται ακριβώς σε μια γραμμή. (Και επιπλέον όχι δύο στην ίδια στήλη.) Αν κάποια γραμμή έχει και άλλους άσσους, όχι από αυτούς τους

δεν με πειράζει. Τώρα που το ξαναβλέπω όμως δεν το διατύπωσα καλά. Διατυπώνοντας την πρώτη μου πρόταση καλύτερα,

«Μπορούμε να βρούμε

άσσους ώστε κάθε γραμμή να εχει ακριβώς 1 από αυτούς τους άσσους και κάθε στήλη να έχει το πολύ ένα από αυτούς τους άσσους»

Γ.-Σ. Σμυρλής έγραψε: Στην "Δεύτερη Περίπτωση" τί ακριβώς λέει το Θεώρημα του Γάμου;

Έχω γράψει ένα άρθρο που το εξηγεί εδώ.

#9

Γ.-Σ. Σμυρλής έγραψε:Συγγνώμη, αλλά εκανα κάποιο λάθος στην διατύπωση το οποίο εδιόρθωσα με κόκκινο χρώμα.

Αυτό ίσως μπέρδεψε τον achilleas, αφού τα αθροίσματα

$m=\displaystyle{\sum_{i,j}\dfrac{a_{ij}}{\sum_{j}a_{ij}}\geq \sum_{i,j}\dfrac{a_{ij}}{\sum_{i}a_{ij}}}=n$ ,

δεν ορίζονται απαραίτητα, δοθέντος ότι οι παρονομαστές ενδέχεται να μηδενίζονται.

Αν υποθέσει ότι και κάθε γραμμή έχει τουλάχιστον ένα άσσο κάτι που επιτρέπεται αλλιώς μπορεί να την διαγράψει τότε η λύση νομίζω πως φτιάχνεται αφού οι παρονομαστές δεν είναι ποτέ μηδέν. (Υπάρχει βέβαια και ένα μικρό πρόβλημα με τους «διπλούς» δείκτες.)

Πίνακας με 1 και 0

Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

Re: Πίνακας με 1 και 0

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