Χρωματισμός κύβου

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #1

Ένας κύβος $n\times n\times n$ διαιρείται σε n^3

στοιχειώδη (ίσα) κυβάκια. Χρησιμοποιώντας n^2

διαφορετικά χρώματα βάφουμε τα στοιχειώδη κυβάκια έτσι ώστε κάθε χρώμα να χρησιμοποιείται ακριβώς

φορές.
Να δειχθεί ότι σε κάποιο γκρουπ

συνεχόμενων κύβων (δηλαδή το αντίστοιχο με τις στήλες και τις σειρές σειρές ενός πίνακα δύο διαστάσεων αλλά στις τρεις διαστάσεις) εμφανίζονται τουλάχιστον $n^{1/3}$ διαφορετικά χρώματα.

#2

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

Γράφουμε a_i,b_i,c_i

για το πλήθος των οριζόντιων, κάθετων και εγκάρσιων γραμμών που περιέχουν το χρώμα

. Έχουμε $a_ib_ic_i \geqslant n$ για κάθε

. Άρα από Holder
$\displaystyle (a_1 + \cdots + a_{n^2})(b_1+\cdots+b_{n^2})(c_1+\cdots+c_{n^2}) \geqslant (\sqrt[3]{a_1b_1c_1} + \cdots +\sqrt[3]{a_{n^2}b_{n^2}c_{n^2}} )^3 \geqslant n^7$

Τότε χωρίς βλάβη της γενικότητας $a_1 + \cdots + a_{n^2} \geqslant n^{7/3}$ . Άρα σε μια από τις οριζόντιες γραμμές θα εμφανίζονται τουλάχιστον $n^{7/3}/n^2 = n^{1/3}$ χρώματα.

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #3

Demetres έγραψε: ↑
Κυρ Μάιος 23, 2021 10:07 am
Μου αρέσουν πολύ τέτοιες ασκήσεις που είναι δύσκολες μεν αλλά έχουν αρκετά σύντομη λύση δε.

Γράφουμε για το πλήθος των οριζόντιων, κάθετων και εγκάρσιων γραμμών που περιέχουν το χρώμα . Έχουμε $a_ib_ic_i \geqslant n$ για κάθε . Άρα από Holder
$\displaystyle (a_1 + \cdots + a_{n^2})(b_1+\cdots+b_{n^2})(c_1+\cdots+c_{n^2}) \geqslant (\sqrt[3]{a_1b_1c_1} + \cdots +\sqrt[3]{a_{n^2}b_{n^2}c_{n^2}} )^3 \geqslant n^7$

Τότε χωρίς βλάβη της γενικότητας $a_1 + \cdots + a_{n^2} \geqslant n^{7/3}$ . Άρα σε μια από τις οριζόντιες γραμμές θα εμφανίζονται τουλάχιστον $n^{7/3}/n^2 = n^{1/3}$ χρώματα.

Πολύ ωραία, δίνω και μία πιθανολογική λύση :
Βάφουμε τυχαία τον κύβο.
Έστω A_i,B_i,C_i

το πλήθος των οριζόντιων, κάθετων και εγκάρσιων λωρίδων $1\times 1\times n$ που περιέχουν το χρώμα

με

.
Για μία οριζόντια γραμμή

(

) ορίζω $a_{j,i}=1$ αν το χρώμα

υπάρχει σε αυτή και $a_{j,i}=0$ αλλιώς.
Τότε στην

εμφανίζονται σύνολο $X_j=\displaystyle \sum _{i=1}^{n^2}a_{j,i}$ χρώματα.
Η αναμενόμενη τιμή αυτής της ποσότητας θα είναι $\displaystyle \mathbb{E}(X_j)=\mathbb{E}(\sum _{i=1}^{n^2}a_{j,i})=\sum_{i=1}^{n^2}\mathbb{E}(a_{j,i})=\sum_{i=1}^{n^2} \mathbb{P}(a_{j,i}=1)=\sum_{i=1}^{n^2} \dfrac{A_i}{n^2}$ .
Έτσι η γενική αναμενόμενη τιμή για όλες τις λωρίδες $1\times 1\times n$ είναι $\displaystyle E=\sum_{i=1}^{n^2} \dfrac{A_i+B_i+C_i}{3n^2}$ .
Σαφώς $A_iB_iC_i\geq n$ .
Έτσι $\displaystyle E\geq \sum_{i=1}^{n^2}\dfrac{3\sqrt[3]{A_iB_iC_i}}{3n^2}\geq \sum_{i=1}^{n^2}\dfrac{ \sqrt[3]{n}}{n^2}=n^{1/3}$ .

Χρωματισμός κύβου

Χρωματισμός κύβου

Re: Χρωματισμός κύβου

Re: Χρωματισμός κύβου

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