Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Al.Koutsouridis · #1

Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016

Θέματα της δεύτερης φάσης (τελικής) για την 10η τάξη. Διάρκεια εξέτασης 3 ώρες.

1. Ο Νίκος πολλαπλασίασε όλους τους διαιρέτες ενός φυσικού αριθμού

. Ο Θοδωρής αύξησε κάθε διαιρέτη κατά 1, και έπειτα πολλαπλασίασε τα αποτελέσματα. Αν το γινόμενο του Θοδωρή διαιρείτε με το γινόμενο του Νίκου, ποιες τιμές μπορεί να πάρει ο

;

2. Δίνονται οι θετικοί αριθμοί $x_{1}, x_{2}, …,x_{n}$ , τέτοιοι, ώστε $x_{i} \leq 2x_{j}$ για $1 \leq i < j \leq n$ . Να δείξετε ότι, μπορούν να βρεθούν θετικοί αριθμοί $y_{1}, \leq y_{2} \leq … \leq y_{n}$ , τέτοιοι, ώστε $x_{k} \leq y_{k} \leq 2x_{k}$ για όλα τα k = 1, 2, …, n

.

3. Ο εγγεγραμμένος κύκλος τριγώνου ABC

εφάπτεται των πλευρών

και

στα σημεία $B_{1}$ και $A_{1}$ αντίστοιχα. Στη πλευρά

βρέθηκε σημείο

τέτοιο, ώστε $AK = KB_{1}$ και $BK=KA_{1}$ . Να δείξετε, ότι $\angle ACB \geq 60^{0}$ .

4. Ο χρωματισμός των κελιών πίνακα $100 \times 100$ με άσπρο και μάυρο χρώμα ονομάζεται «επιτρεπτός», αν σε κάθε γραμμή και κάθε στήλη υπάρχουν από 50 έως 60 μαύρα κελιά. Σε έναν επιτρεπτό χρωματισμό επιτρέπεται να αλλάξουμε το χρώμα ενός κελιού αν ο χρωματισμός παραμείνει επιτρεπτός. Να δείξετε ότι με μια τέτοια διαδικασία μπορούμε από οποιαδήποτε επιτρεπτό χρωματισμό να καταλήξουμε σε οποιοδήποτε άλλο επιτρεπτό χρωματισμό.

Καταληκτική αίθουσα (*)

5. Έστω

μια ευθεία και

,

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

με την υποτείνουσά τους επί της

. Να αποδείξετε ότι, οι περιγεγραμμένοι κύκλοι των τριγώνων PBC

, έχουν και ένα άλλο κοινό σημείο εκτός από το

.

6. Τεθλασμένη 100 πλευρών, της οποίας καμία τριάδα πλευρών δεν διέρχεται από το ίδιο σημείο, είναι εγγεγραμμένη σε κύκλο. Εξάλλου όλες οι γωνιές της είναι αμβλείες και το άθροισμά τους σε μοίρες διαιρείτε με το 720. Να αποδείξετε, ότι αυτή η τεθλασμένη έχει περιττό αριθμό σημείων τομής με τον εαυτό της.

7. Το πολυώνυμο P(x)

με ακέραιους συντελεστές και ο θετικός ακέραιος a > 1

είναι τέτοιοι, ώστε για κάθε ακέραιο

υπάρχει ένας ακέραιος

για τον οποίο

aP(x) = P(z)

Nα βρείτε όλα τα ζεύγη (P(x), a)

με την παραπάνω ιδιότητα.

(*) Όσοι έλυσαν δυο από τα τέσσερα αρχικά προβλήματα καλέστηκαν να λύσουν άλλα τρία σε διαφορετική αίθουσα. Ο επιπλέον χρόνος που δίνεται είναι μια ώρα.

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

$\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{\gr τάξη} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \text{\gr σύνολο} &\text{\gr καταληκτική} \\ \hline 10 & 19 & 68 & 35 & 3 & 10 & 3 & 0 & 126 & 36 \\ \hline \end{tabular}$

$\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \text{\gr τάξη} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 10 & 42 & 21 & 10 & 2 & 2 & 1 & 0 \\ \hline \end{tabular}$

JimNt. · #2

Al.Koutsouridis έγραψε:Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016

Θέματα της δεύτερης φάσης (τελικής) για την 10η τάξη. Διάρκεια εξέτασης 3 ώρες.

1. Ο Νίκος πολλαπλασίασε όλους τους διαιρέτες ενός φυσικού αριθμού . Ο Θοδωρής αύξησε κάθε διαιρέτη κατά 1, και έπειτα πολλαπλασίασε τα αποτελέσματα. Αν το γινόμενο του Θοδωρή διαιρείτε με το γινόμενο του Νίκου, ποιες τιμές μπορεί να πάρει ο ;

Ορίζουμε τους διαιρέτες του

:

. Tότε πρέπει A|B

,όπου $A=d_2\cdot \cdot....n$ , B=2(d_3+1).....(n+1)

. Διακρίνουμε

περιπτώσεις:
$2\nmid n$ Υποθέτουμε ότι ο

έχει $\ge 2$ διαιρέτες (δηλαδή είναι διάφορος του

) Συνεπώς όλοι οι διαρέτες του

είναι περιττοί και άρα όλοι οι παράγοντες του

άρτιοι. Πρέπει $A=d_2\cdot \cdot....n|2^{k+1}\cdot \frac{(d_2+1)}{2}.....\frac{(n+1)}{2}$ . Και αφού $(A,2^{k+1})=1$ πρέπει $A=d_2\cdot \cdot....n|C=\frac{(d_2+1)}{2}.....\frac{(n+1)}{2}$ . Όμως για κάθε a>1

ισχύει $a>\frac{a+1}{2}$ , συνεπώς θα ισχύει A>C

, άτοπο. Άρα η μόνη λύση εδώ είναι $\boxed{n=1}$ , που ικανοποιεί.
$2\mid n$ Υποθέτουμε ότι ο

έχει $\ge 4$ διαιρέτες (δηλαδή είναι διάφορος του

,

). Προφανώς είναι d_2=2

. Έχουμε $A=2\cdot d_3 ....n$ και B=6(d_3+1).....(n+1)

. Πρέπει λοιπόν $D=d_3\cdot ....n|3(d_3+1).....(n+1)$ . Είναι όμως (n,n+1)=1

και επομένως (d_i,n+1)=1

. Άρα πρέπει $D=d_3\cdot ....n|E=3(d_3+1)......(d_{k-1}+1)$ . Θα δείξουμε επαγωγικά ότι $d_3\cdot......n>3(d_3+1)......(d_{k-1}+1)$ . Έστω για ένα

ισχύει ότι $d_3\cdot.....d_l>3(d_3+1).......(d_{l-1}+1)$ (1)

. Θα δείξουμε ότι ισχύει και για l+1

. Πρέπει να δείξουμε ότι $d_3\cdot.....d_l\cdot d_{l+1}>3(d_3+1).......(d_{l-1}+1)(d_l+1)$ . Είναι προφανές πως $d_{l+1}>d{l}+1$ (αφού ο $d_{l}$ αποτελεί τον δεύτερο μεγαλύτερο διαιρέτη του $d_{l+1}$ (μετά από τον ίδιο) και άρα θα ισχύει $\frac{d_{l+1}}{2}>d_l$ $\Leftrightarrow$ $d_{l+1}>2d_l>d_l+1$ , αυτό που θέλαμε). Έτσι με πολλαπλασιασμό με την (1)

προκύπτει αυτό που θέλαμε. Συνεπώς παίρνουμε την περίπτωση k=4

. Θα δείξουμε ότι $d_3\cdot d_4>3(d_3+1)$ , που είναι προφανές αφού $d_3\ge3$ και d_4>d_3+1

για τον λόγο που δείξαμε παραπάνω. Συνεπώς, αφού ισχύει ότι για k=4

και άρα $D\nmid E$ θα ισχύει για κάθε $k\ge 4$ . Συνεπώς, ελέγχοντας τις περιπτώσεις n=2,4

παίρνουμε $\boxed{n=2}$ .

#3

Al.Koutsouridis έγραψε:Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016
Καταλληκτική αίθουσα (*)
5. Έστω μια ευθεία και , δυο σημεία εκτός αυτής. Θεωρούμε όλα τα δυνατά ορθογώνια τρίγωνα με την υποτείνουσά τους επί της . Να αποδείξετε ότι, οι περιγεγραμμένοι κύκλοι των τριγώνων , έχουν και ένα άλλο κοινό σημείο εκτός από το .

Καλό!!

Έστω

το ύψος του τριγώνου ABC

, και, ας δούμε την δύναμη του σημείου

ως προς τον κύκλο PBC

. Αυτή είναι σταθερή αφού (BD)(DC)=AD^2

.

Αν η

επανατέμνει τον κύκλο στο

, τότε το

είναι σταθερό, αφού, (ED)(DP)=AD^2

. Άρα όλοι οι κύκλοι διέρχονται και από το

mikemoke · #4

[quote="Al.Koutsouridis"]Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016

4. Ο χρωματισμός των κελιών πίνακα $100 \times 100$ με άσπρο και μάυρο χρώμα ονομάζεται «επιτρεπτός», αν σε κάθε γραμμή και κάθε στήλη υπάρχουν από 50 έως 60 μαύρα κελιά. Σε έναν επιτρεπτό χρωματισμό επιτρέπεται να αλλάξουμε το χρώμα ενός κελιού αν ο χρωματισμός παραμείνει επιτρεπτός. Να δείξετε ότι με μια τέτοια διαδικασία μπορούμε από οποιαδήποτε επιτρεπτό χρωματισμό να καταλήξουμε σε οποιοδήποτε άλλο επιτρεπτό χρωματισμό.

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

Al.Koutsouridis · #5

mikemoke έγραψε:
Al.Koutsouridis έγραψε:Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016

4. Ο χρωματισμός των κελιών πίνακα $100 \times 100$ με άσπρο και μάυρο χρώμα ονομάζεται «επιτρεπτός», αν σε κάθε γραμμή και κάθε στήλη υπάρχουν από 50 έως 60 μαύρα κελιά. Σε έναν επιτρεπτό χρωματισμό επιτρέπεται να αλλάξουμε το χρώμα ενός κελιού αν ο χρωματισμός παραμείνει επιτρεπτός. Να δείξετε ότι με μια τέτοια διαδικασία μπορούμε από οποιαδήποτε επιτρεπτό χρωματισμό να καταλήξουμε σε οποιοδήποτε άλλο επιτρεπτό χρωματισμό.

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

Ναι ίσως είναι λίγο ασαφής. Μια καλύτερη απόδοση θα ηταν:

"Ο χρωματισμός των κελιών πίνακα $100 \times 100$ με άσπρο και μάυρο χρώμα ονομάζεται «επιτρεπτός», αν σε κάθε γραμμή και κάθε στήλη υπάρχουν από 50 έως 60 μαύρα κελιά. Επιτρέπεται να αλλάξουμε το χρώμα ενός εκ των κελιών επιτρεπτού χρωματισμού, αν αυτός παραμένει επιτρεπτός. Να αποδείξετε, ότι με μια τέτοια διαδικασία (κινήσεις) μπορούμε από οποιαδήποτε επιτρεπτό χρωματισμό να καταλήξουμε (πάρουμε) σε οποιοδήποτε άλλο επιτρεπτό χρωματισμό."

Οπότε ναι ενός και μόνου κελιού αλλά όχι απαραίτητα μια και μόνο φορά (δεν προκύπτει από την εκφώνηση).

Να σημειώσω ότι δεν έχω λύσει το πρόβλημα.

mikemoke · #6

4. Ο χρωματισμός των κελιών πίνακα $100 \times 100$ με άσπρο και μάυρο χρώμα ονομάζεται «επιτρεπτός», αν σε κάθε γραμμή και κάθε στήλη υπάρχουν από 50 έως 60 μαύρα κελιά. Σε έναν επιτρεπτό χρωματισμό επιτρέπεται να αλλάξουμε το χρώμα ενός κελιού αν ο χρωματισμός παραμείνει επιτρεπτός. Να δείξετε ότι με μια τέτοια διαδικασία μπορούμε από οποιαδήποτε επιτρεπτό χρωματισμό να καταλήξουμε σε οποιοδήποτε άλλο επιτρεπτό χρωματισμό.

Αν εχουμε τον ελαχιστο αριθμο μαυρων κελιων 50*50 ενασ επιτρεπτοσ τροπος να τα βαψουμε ειναι η κλασικη σκακιερα Μ-Α-Μ ... Με τουσ καταλληλους μετασχηματισμους τησ σκακιερας θα δειξουμε οτι μπορουν να προκυψουν ολοι οι υπολοιποι επιτρεπτοι χρωματισμοι και αρα και το αντιστροφο
Αν ο αριθμος των μαυρων κελιων μεινει αμεταβλητος 50*50 τοτε μπορουμε να μετασχηματισουμε την σκακιερα σε ολουσ τους υπολοιπουσ εναλλασoντας μαυρα κελια σε δυο διαδοχικες οριζοντιες ή κατακορυφες στηλες .Με αλλα λογια αν '' αναιβει '' ενα μαυρο κελι σε μια διπλανη του στηλη τοτε ενα απτα μαυρα κελια της διπλανης πρεπει να ''πεσει'' .Αυτο μπορει να γινει οσεσ φορεσ επιθημουμε εξασφαλιζoντασ ολους τουσ δυνατουσ χρωματισμους. Αν προσθεσουμε 1,2,3...(μεχρι να φτασουμε το μεγιστο) μαυρα κελια τοτε με την ιδια στρατηγικη προκυπτουν ολοι οι υπολοιποι χρωματισμοι .

Σημειωση Φανταζομαστε τους μετασχηματισμους σαν να σερνουμε τα μαυρα κελια πανω σε μια ασπρη επιφανεια οπως τα sliding puzzle

Al.Koutsouridis · #7

mikemoke έγραψε:
Αν εχουμε τον ελαχιστο αριθμο μαυρων κελιων 50*50 ενασ επιτρεπτοσ τροπος να τα βαψουμε ειναι η κλασικη σκακιερα Μ-Α-Μ ... Με τουσ καταλληλους μετασχηματισμους τησ σκακιερας θα δειξουμε οτι μπορουν να προκυψουν ολοι οι υπολοιποι επιτρεπτοι χρωματισμοι και αρα και το αντιστροφο
Αν ο αριθμος των μαυρων κελιων μεινει αμεταβλητος 50*50 τοτε μπορουμε να μετασχηματισουμε την σκακιερα σε ολουσ τους υπολοιπουσ εναλλασoντας μαυρα κελια σε δυο διαδοχικες οριζοντιες ή κατακορυφες στηλες .Με αλλα λογια αν '' αναιβει '' ενα μαυρο κελι σε μια διπλανη του στηλη τοτε ενα απτα μαυρα κελια της διπλανης πρεπει να ''πεσει'' .Αυτο μπορει να γινει οσεσ φορεσ επιθημουμε εξασφαλιζoντασ ολους τουσ δυνατουσ χρωματισμους. Αν προσθεσουμε 1,2,3...(μεχρι να φτασουμε το μεγιστο) μαυρα κελια τοτε με την ιδια στρατηγικη προκυπτουν ολοι οι υπολοιποι χρωματισμοι .

Σημειωση Φανταζομαστε τους μετασχηματισμους σαν να σερνουμε τα μαυρα κελια πανω σε μια ασπρη επιφανεια οπως τα sliding puzzle

Καλημέρα,

Μπορείς να εξηγήσεις λίγο πιο αναλυτικά την λύση σου; Ειδικά το κομμάτι με κόκκινο της τελευταίας πρότασης. Δυσκολεύομαι να "πιάσω" τον αλγόριθμο που περιγράφεις αλλά και το πεπερασμένο του αλγορίθμου.

mikemoke · #8

Al.Koutsouridis έγραψε:
mikemoke έγραψε:
Αν εχουμε τον ελαχιστο αριθμο μαυρων κελιων 50*50 ενασ επιτρεπτοσ τροπος να τα βαψουμε ειναι η κλασικη σκακιερα Μ-Α-Μ ... Με τουσ καταλληλους μετασχηματισμους τησ σκακιερας θα δειξουμε οτι μπορουν να προκυψουν ολοι οι υπολοιποι επιτρεπτοι χρωματισμοι και αρα και το αντιστροφο
Αν ο αριθμος των μαυρων κελιων μεινει αμεταβλητος 50*50 τοτε μπορουμε να μετασχηματισουμε την σκακιερα σε ολουσ τους υπολοιπουσ εναλλασoντας μαυρα κελια σε δυο διαδοχικες οριζοντιες ή κατακορυφες στηλες .Με αλλα λογια αν '' αναιβει '' ενα μαυρο κελι σε μια διπλανη του στηλη τοτε ενα απτα μαυρα κελια της διπλανης πρεπει να ''πεσει'' .Αυτο μπορει να γινει οσεσ φορεσ επιθημουμε εξασφαλιζoντασ ολους τουσ δυνατουσ χρωματισμους. Αν προσθεσουμε 1,2,3...(μεχρι να φτασουμε το μεγιστο) μαυρα κελια τοτε με την ιδια στρατηγικη προκυπτουν ολοι οι υπολοιποι χρωματισμοι .

Σημειωση Φανταζομαστε τους μετασχηματισμους σαν να σερνουμε τα μαυρα κελια πανω σε μια ασπρη επιφανεια οπως τα sliding puzzle
Καλημέρα,

Μπορείς να εξηγήσεις λίγο πιο αναλυτικά την λύση σου; Ειδικά το κομμάτι με κόκκινο της τελευταίας πρότασης. Δυσκολεύομαι να "πιάσω" τον αλγόριθμο που περιγράφεις αλλά και το πεπερασμένο του αλγορίθμου.

Καλησπερα,

Στην σκακιερα αν τον αριθμο των στοιχειων (μαυρα κελια) δεν τον μεταβαλουμε (παραμενει 50*50) .Τοτε με μεταφορα ενος στοιχειου σε κενο (ασπρο κελι) μπορουν να προκυψουν ολοι οι πιθανοι χρωματισμοι 50*50 (επιτρεπτοι και μη) .Θα δειξω πως μονο η στρατηγικη που περιεγραψα εξασφαλιζει επιτρεπτους χρωματισμους .Ας υποθεσουμε οτι μεταφερουμε ενα στοιχειο απτο κελι Α1 σε ενα αλλο(πχ Ε6) το οποιο δεν βρισκεται στην Α κατακορυφη ουτε στην 1 οριζοντια ,δηλαδη σε ενα μη διπλανο ,τοτε ο χρωματισμος ειναι μη επιτρεπτος γιατι η Ε και 6 εχουν ενα παραπανω ενω η Α και 1 ενα λιγοτερο.Ναι, αλλα αν προσπαθησω να διορθωσω το σφαλμα μεταφεροντας στοιχεια απτη Ε ή 6 στην Α ή 1 δημιουργειται το ιδιο προβλημα .Αρα παγιδευομαι σε ενα loop (ατερμων βρογχο) σφαλματων .Επομενως ο μονος τροπος που εξασφαλιζει επιτρεπτους χρωματισμους ειναι η μεταφορα στοιχειων σε διπλανη στηλη. Και αυτο επειδη μπορει να ισοσταθμιστει ο αριθμος των στοιχειων

Τωρα στην σκακιερα εαν προσθεσω ενα στοιχειο σε ενα κενο μεταβαλλοντας τον αριθμο σε 50*50+1 και με τους μετασχηματισμους δεν μεταβαλλω τον αριθμο αυτο (Αυτο θα γινει μεταφεροντας στοιχεια σε κενο ) τοτε, οπως πριν, οι μονοι μετασχηματισμοι που δινουν επιτρεπτο ειναι μεταφορα σε κενο της διπλανης στηλης .Το ιδιο ισχυει και για 50*50 +2,+3,+4,...,+60*60-50*50 .Θα πρεπει να προσεξουμε να μην γινει υπερκορεσμος της στηλης .

Ετσι διχνουμε οτι μπορουμε να καταληξουμε απο την σκακιερα σε ολουσ τους αλλους χρωματισμους και το αντιστροφο.

nikkru · #9

Al.Koutsouridis έγραψε:Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015-2016

Θέματα της δεύτερης φάσης (τελικής) για την 10η τάξη. Διάρκεια εξέτασης 3 ώρες.

3. Ο εγγεγραμμένος κύκλος τριγώνου εφάπτεται των πλευρών και στα σημεία $B_{1}$ και $A_{1}$ αντίστοιχα. Στη πλευρά βρέθηκε σημείο τέτοιο, ώστε $AK = KB_{1}$ και $BK=KA_{1}$ . Να δείξετε, ότι $\angle ACB \geq 60^{0}$ .

: Πετρούπολη 2016_Φ2_Τ10_3.png (12.66 KiB) Προβλήθηκε 1354 φορές

Από τα δεδομένα είναι οι κόκκινες γωνίες μεταξύ τους ίσες όπως και οι μπλε.

Έτσι, $A_1\widehat{K}B_1=180^o-(180^o-2\widehat{B}+180^o-2\widehat{A})=2\widehat{A}+2\widehat{B}-180^o=\widehat{A}+\widehat{B}-\widehat{C}$ .

Αν το σημείο $K\equiv C_1$ τότε $A_1\widehat{K}B_1=\displaystyle{ \frac {\overset{\frown }{A_1B_1 } }{2}}$ , διαφορετικά το

είναι εξωτερικό του κύκλου οπότε

$A_1\widehat{K}B_1=\displaystyle{ \frac {\overset{\frown }{A_1B_1 } }{2}-\frac {\overset{\frown }{TP } }{2}}<\frac {\overset{\frown }{A_1B_1 } }{2}$ . Άρα σε κάθε περίπτωση είναι $A_1\widehat{K}B_1\leq\displaystyle{ \frac {\overset{\frown }{A_1B_1 } }{2}}$ .

Αφού $\widehat{C}=\displaystyle{ \frac {\overset{\frown }{A_1B_1 } }{2}}$ , είναι $\widehat{A}+\widehat{B}-\widehat{C}\leq\widehat{C}\Leftrightarrow \widehat{A}+\widehat{B}+\widehat{C}\leq3\widehat{C}\Leftrightarrow \boxed{60^o\leq\widehat{C}}$

mikemoke · #10

mikemoke έγραψε:
Al.Koutsouridis έγραψε:
mikemoke έγραψε:
Αν εχουμε τον ελαχιστο αριθμο μαυρων κελιων 50*50 ενασ επιτρεπτοσ τροπος να τα βαψουμε ειναι η κλασικη σκακιερα Μ-Α-Μ ... Με τουσ καταλληλους μετασχηματισμους τησ σκακιερας θα δειξουμε οτι μπορουν να προκυψουν ολοι οι υπολοιποι επιτρεπτοι χρωματισμοι και αρα και το αντιστροφο
Αν ο αριθμος των μαυρων κελιων μεινει αμεταβλητος 50*50 τοτε μπορουμε να μετασχηματισουμε την σκακιερα σε ολουσ τους υπολοιπουσ εναλλασoντας μαυρα κελια σε δυο διαδοχικες οριζοντιες ή κατακορυφες στηλες .Με αλλα λογια αν '' αναιβει '' ενα μαυρο κελι σε μια διπλανη του στηλη τοτε ενα απτα μαυρα κελια της διπλανης πρεπει να ''πεσει'' .Αυτο μπορει να γινει οσεσ φορεσ επιθημουμε εξασφαλιζoντασ ολους τουσ δυνατουσ χρωματισμους. Αν προσθεσουμε 1,2,3...(μεχρι να φτασουμε το μεγιστο) μαυρα κελια τοτε με την ιδια στρατηγικη προκυπτουν ολοι οι υπολοιποι χρωματισμοι .

Σημειωση Φανταζομαστε τους μετασχηματισμους σαν να σερνουμε τα μαυρα κελια πανω σε μια ασπρη επιφανεια οπως τα sliding puzzle
Καλημέρα,

Μπορείς να εξηγήσεις λίγο πιο αναλυτικά την λύση σου; Ειδικά το κομμάτι με κόκκινο της τελευταίας πρότασης. Δυσκολεύομαι να "πιάσω" τον αλγόριθμο που περιγράφεις αλλά και το πεπερασμένο του αλγορίθμου.
Καλησπέρα,

Στην σκακιέρα αν τον αριθμό των στοιχείων (μαυρά κελιά) δεν τον μεταβάλουμε (παραμένει 50*50) .Τοτε με μεταφορά ενος στοιχείου σε κενό (άσπρο κελί) μπορούν να προκύψουν όλοι οι πιθανοί χρωματισμοί 50*50 (επιτρεπτοί και μη) .Θα δείξω πως μόνο η στρατηγική που περιέγραψα εξασφαλίζει επιτρεπτούς χρωματισμούς .Ας υποθέσουμε οτι μεταφέρουμε ενα στοιχείο απτο κελί Α1 σε ενα άλλο(πχ Ε6) το οποίο δεν βρίσκεται στην Α κατακόρυφη ουτε στην 1 οριζόντια ,δηλαδή σε ενα μη διπλανό ,τότε ο χρωματισμός ειναι μη επιτρεπτός γιατί η Ε και 6 έχουν ενα παραπένω ενώ η Α και 1 ενα λιγότερο.Ναι, αλλά αν προσπαθήσω να διορθώσω το σφάλμα μεταφέροντας στοιχεία απτή Ε ή 6 στην Α ή 1 δημιουργείται το ιδίο πρόβλημα .Άρα παγιδεύομαι σε ενα loop (ατέρμων βρόγχο) σφαλμάτων .Επομένως ο μόνος τρόπος που εξασφαλίζει επιτρεπτούς χρωματισμούς ειναι η μεταφορά στοιχείων σε διπλανή στηήλη. Και αυτό επειδή μπορεί να ισοσταθμίστει ο αριθμός των στοιχείων

Τωρα στην σκακιερα εαν προσθεσω ενα στοιχειο σε ενα κενο μεταβαλλοντας τον αριθμο σε 50*50+1 και με τους μετασχηματισμους δεν μεταβαλλω τον αριθμο αυτο (Αυτο θα γινει μεταφεροντας στοιχεια σε κενο ) τοτε, οπως πριν, οι μονοι μετασχηματισμοι που δινουν επιτρεπτο ειναι μεταφορα σε κενο της διπλανης στηλης .Το ιδιο ισχυει και για 50*50 +2,+3,+4,...,+60*60-50*50 .Θα πρεπει να προσεξουμε να μην γινει υπερκορεσμος της στηλης .

Ετσι διχνουμε οτι μπορουμε να καταληξουμε απο την σκακιερα σε ολουσ τους αλλους χρωματισμους και το αντιστροφο.

Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015/16 (ΦΙΙ τάξη 10)

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