Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1362
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

#1

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Οκτ 20, 2016 8:29 pm

1. Μία συσκευή μνήμης υπολογιστή έχει τη μορφή ορθογωνίου παραλληλογράμμου ακέραιων διαστάσεων a \times b \ (a, b \geqslant 2) χωρισμένου σε κελιά 1 \times 1 έτσι ώστε σε κάθε κελί να αποθηκεύεται ένα bit (δυαδικό ψηφίο, 0 ή 1). Για τεχνικούς λόγους το άθροισμα κάθε σειράς και κάθε στήλης πρέπει να είναι περιττό. Πόσες διαφορετικές διατάξεις μπορούν να αποθηκευτούν;

2. Ένα πιο σύγχρονο μοντέλο χρησιμοποιεί ένα παραλληλεπίπεδο ακέραιων διαστάσεων a \times b \times c \ (a, b, c \geqslant 2) χωρισμένο σε κελιά 1 \times 1 \times 1 στα οποία αποθηκεύεται ένα bit. Και πάλι το άθροισμα των περιεχομένων των κελιών κατά μήκος μιας διάστασης (κρατώντας τις άλλες δύο σταθερές) πρέπει να είναι περιττό. Πόσες διαφορετικές διατάξεις μπορούν να αποθηκευτούν;
τελευταία επεξεργασία από dement σε Δευ Οκτ 23, 2017 1:41 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.

Λέξεις Κλειδιά:
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 10161
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

#2

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Πέμ Οκτ 20, 2016 10:52 pm

.
Όμοιο με αυτό. Το θυμήθηκα γιατί μου είχε κάνει πολλή εντύπωση.


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1362
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

#3

Μη αναγνωσμένη δημοσίευση από dement » Τρί Οκτ 25, 2016 3:06 pm

Επαναφορά (παρά την ομοιότητα με το θέμα που παραπέμπει ο Μιχάλης, υπάρχουν και διαφορές).


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 676
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τρί Οκτ 25, 2016 8:28 pm

dement έγραψε:1. Μία συσκευή μνήμης υπολογιστή έχει τη μορφή ορθογωνίου παραλληλογράμμου ακέραιων διαστάσεων a \times b \ (a, b \geqslant 2) χωρισμένου σε κελιά 1 \times 1 έτσι ώστε σε κάθε κελί να αποθηκεύεται ένα bit (δυαδικό ψηφίο, 0 ή 1). Για τεχνικούς λόγους το άθροισμα κάθε σειράς και κάθε στήλης πρέπει να είναι περιττό. Πόσες διαφορετικές διατάξεις μπορούν να αποθηκευτούν;
Θα δείξουμε ότι όταν τα a και b είναι το ένα είναι άρτιο και το άλλο περιττό τότε δεν υπάρχει καμία διάταξη, ενώ όταν είναι
και τα δύο άρτια ή και τα δύο περιττά τότε θα έχουμε 2^{(a-1)(b-1)} διατάξεις.

1) Αν τα a και b είναι το ένα είναι άρτιο και το άλλο περιττό.

Φαίνεται εύκολα σε πίνακα 2 \times 3 ότι δεν υπάρχει σωστή διάταξη αλλά θα το γενικεύσουμε.

\begin{tabular}{|c|c|c|} \hline 1 & 0 & 1 \\ \hline 0 & 1 & 0 \\  \hline \end{tabular}

Έστω ότι το a είναι άρτιος αριθμός και το b είναι περιττός. Ας υποθέσουμε ότι είναι εφικτή μια διάταξη με περιττό άθροισμα ανά γραμμή και ανά στήλη. Αν S_1 το άθροισμα των αθροισμάτων ανά γραμμή τότε, επειδή προκύπτει από άρτιο πλήθος περιττών προσθετέων, θα είναι άρτιος αριθμός. Αν S_2 το άθροισμα των αθροισμάτων ανά στήλη τότε, επειδή προκύπτει από περιττό πλήθος περιττών προσθετέων, θα είναι περιττός αριθμός. Όμως επειδή πρέπει S_1 = S_2 καταλήγουμε σε άτοπο. Το ίδιο γίνεται και όταν το a είναι περιττός και το b άρτιος.

2) Αν τα a και b είναι και τα δύο άρτια ή και τα δύο περιττά.

Γεμίζουμε όλο τον πίνακα στην τύχη με 0 και 1, εκτός από την τελευταία γραμμή και την τελευταία στήλη. Θα έχουμε 2^{(a-1)(b-1) διαφορετικές διατάξεις.

Η συμπλήρωση του τελευταίου κελιού κάθε μιας από τις a-1 πρώτες γραμμές γίνεται με μοναδικό τρόπο. Έτσι αν η γραμμή έχει ήδη περιττό αριθμό από 1 τότε βάζουμε 0 αλλιώς βάζουμε 1.

Το ίδιο γίνεται για το τελευταίο κελί κάθε μιας από τις b-1 πρώτες στήλες.

Στο τελευταίο κελί της τελευταίας γραμμής, που ταυτίζεται με το τελευταίο κελί της τελευταίας στήλης, θα βάλουμε με μοναδικό τρόπο 0 ή 1 ώστε η τελευταία γραμμή να έχει περιττό αριθμό από 1 και θα δείξουμε παρακάτω ότι έτσι θα έχει περιττό αριθμό από 1 και η τελευταία στήλη.

Έτσι θα έχουμε τελικά \boxed{2^{(a-1)(b-1)}} διαφορετικές διατάξεις.

Για να κλείσουμε την εκκρεμότητα με το τελευταίο κελί ας δούμε μια διαφορετική διαδικασία.
Έστω D μία από τις 2^{(a-1)(b-1)} διαφορετικές διατάξεις, η οποία θα έχει n ψηφία ίσα με 1 στα πρώτα (a-1) \times (b-1)} κελιά.

Ακολουθούμε τα εξής βήματα:

Ξεκινάμε με έναν πίνακα A που θα έχει παντού 0 εκτός από την τελευταία γραμμή και την τελευταία στήλη που θα έχει παντού 1. Ειδικά το τελευταίο κελί θα έχει 0 αν τα a και b είναι και τα δύο άρτια, ενώ θα έχει 1 αν τα a και b είναι και τα δύο περιττά. Π.χ.

\begin{tabular}{|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 & 0 & 1  \\ \hline 0 & 0 & 0 & 0 & 0 & 1  \\ \hline 0 & 0 & 0 & 0 & 0 & 1  \\ \hline 1 & 1 & 1 & 1 & 1 & 0  \\ \hline  \end{tabular}

ή

\begin{tabular}{|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 & 1  \\ \hline 0 & 0 & 0 & 0 & 1  \\ \hline 1 & 1 & 1 & 1 & 1  \\ \hline  \end{tabular}

Με αυτόν τον τρόπο ο πίνακας θα έχει ήδη περιττά αθροίσματα ανά γραμμή και ανά στήλη.

Για κάθε ένα ψηφίο 1 από τα n της διάταξης D αντικαθιστούμε στην αντίστοιχη θέση του πίνακα A το 0 με 1. Ταυτόχρονα θα αλλάζει (από 1 σε 0, ή από 0 σε 1 αν έχει ήδη αλλάξει από προηγούμενο βήμα) το τελευταίο κελί της αντίστοιχης γραμμής αλλά και της αντίστοιχης στήλης ώστε τα αθροίσματά τους να παραμένουν περιττά. Και ταυτόχρονα θα αλλάζει το τελευταίο κελί του πίνακα. Επομένως σε κάθε βήμα όλες οι γραμμές και όλες οι στήλες θα συνεχίζουν να έχουν περιττά αθροίσματα.

Μάλιστα, αν το n είναι άρτιο τότε το τελευταίο κελί του πίνακα θα έχει το ίδιο ψηφίο με το οποίο ξεκίνησε η διαδικασία, ενώ αν το n είναι περιττό το τελευταίο κελί θα έχει αλλάξει.

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

Προφανώς χωρίς αυτήν δεν θα μπορούσα να βρω καμία λύση.


Houston, we have a problem!
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 676
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2016-17 (2)

#5

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τρί Οκτ 25, 2016 11:02 pm

dement έγραψε: 2. Ένα πιο σύγχρονο μοντέλο χρησιμοποιεί ένα παραλληλεπίπεδο ακέραιων διαστάσεων a \times b \times c \ (a, b, c \geqslant 2) χωρισμένο σε κελιά 1 \times 1 \times 1 στα οποία αποθηκεύεται ένα bit. Και πάλι το άθροισμα των περιεχομένων των κελιών κατά μήκος μιας διάστασης (κρατώντας τις άλλες δύο σταθερές) πρέπει να είναι περιττό. Πόσες διαφορετικές διατάξεις μπορούν να αποθηκευτούν;
Αν η λύση στο 1ο ερώτημα είναι σωστή, τότε συνδυάζοντας κάθε φορά τις δύο από τις τρεις διαστάσεις θα έχουμε τους ίδιους περιορισμούς, ενώ η σχετική μέθοδος επεκτείνεται (μάλλον!) εύκολα και στην τρίτη διάσταση.

Επομένως, όταν τα a, b και c είναι όλα άρτια ή όλα περιττά τότε θα έχουμε 2^{(a-1)(b-1)(c-1)} διατάξεις, ενώ σε κάθε άλλη περίπτωση δεν θα έχουμε καμία.


Houston, we have a problem!
Απάντηση

Επιστροφή σε “Διάφορα άλλα θέματα εξετάσεων”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης