2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

[Datis-Kalali]

1)Έχουμε θέσεις και () με πεπεράσμενο πλήθο κάρτες. Σε κάθε βήμα μπορούμε να κάνουμε ένα απο τα εξής βήματα:
i. Αν στην θέση έχουμε τουλάχιστον 3 κάρτες, τότε μπορούμε να πάρουμε 3 κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις , και . (Θεωρούμε και )
ii. Αν στην θέση έχουμε τουλάχιστον κάρτες, τότε μπορούμε να πάρουμε κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις , ,..., .
Να δείξετε ότι αν έχουμε τουλάχιστον κάρτες συνολίκα, τότε μέτα απο ένα πεπερασμένο πλήθο βήματων, μπορούμε να να έχουμε τουλάχιστον σε κάθε θέση.
(Πήγη: Περσική ιστοσελίδα μαθηματικών)
2)Να βρείτε όλοι οι τετραψηφίο αριθμοί , έτσι ώστε:

(Πήγη: Ολυμπιάδα Czech 2000)

[Demetres]

1)Έχουμε θέσεις και () με πεπεράσμενο πλήθο κάρτες. Σε κάθε βήμα μπορούμε να κάνουμε ένα απο τα εξής βήματα:
i. Αν στην θέση έχουμε τουλάχιστον 3 κάρτες, τότε μπορούμε να πάρουμε 3 κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις , και . (Θεωρούμε και )
ii. Αν στην θέση έχουμε τουλάχιστον κάρτες, τότε μπορούμε να πάρουμε κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις , ,..., .
Να δείξετε ότι αν έχουμε τουλάχιστον κάρτες συνολίκα, τότε μέτα απο ένα πεπερασμένο πλήθο βήματων, μπορούμε να να έχουμε τουλάχιστον σε κάθε θέση.
(Πήγη: Περσική ιστοσελίδα μαθηματικών)

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

Μπορούμε λοιπόν να καταλήξουμε σε μια κατάσταση όπου σε κάθε θέση θα έχουμε από μέχρι κάρτες. Τώρα επαναλαμβάνουμε το βήμα (ii) μέχρις ούτω να συμβεί ένα από τα πιο κάτω
(α) Σε κάθε θέση υπάρχουν τουλάχιστον κάρτες.
(β) Δεν μπορούμε πλέον να επαναλάβουμε το βήμα (ii) επειδή δεν υπάρχουν αρκετές κάρτες στην θέση .

Ισχυρίζομαι ότι αυτό που θα συμβεί είναι το (α), πιθανώς ταυτόχρονα με το (β). Πράγματι αν δεν συμβεί το (α), τότε θα υπάρχει ώστε σε κάθε θέση να έχω από μέχρι κάρτες, ενώ στην θέση να έχω το πολύ κάρτες. Τότε όμως συνολικά θα είχα το πολύ



κάρτες, άτοπο.

Είμαι τώρα σε μια κατάσταση όπου
(Α) Κάθε θέση έχει από έως κάρτες.
(Β) Υπάρχει τουλάχιστον μια θέση με ακριβώς κάρτες.

Βρίσκω τώρα, αν υπάρχει, ακολουθία θέσεων ώστε
(1) Στα υπάρχουν από κάρτες.
(2) Στα υπάρχουν από τουλάχιστον κάρτες.
(3) Δεν υπάρχουν κάρτες ούτε στο ούτε στο .

Τότε εκτελώ το βήμα (i) διαδοχικά στις θέσεις . Τότε στις θέσεις θα μειωθεί το πλήθος των καρτών κατά , στις θέσεις θα μειωθεί το πλήθος των καρτών κατά , και στις θέσεις θα αυξηθεί το πλήθος των καρτών κατά . Άρα πάλι θα είμαστε σε μια κατάσταση όπου τα (Α) και (Β) ισχύουν. [Πρέπει να ελέγξουμε τι συμβαίνει αν διότι τότε το πλήθος των καρτών σε αυτήν την θέση θα αυξηθεί κατά . Αλλά σε αυτήν την περίπτωση αυτή η θέση θα είχε αρχικά κάρτες λόγω του (Β).

Επειδή όποτε εκτελώ το πιο πάνω, το πλήθος των καρτών στις θέσεις μειώνεται, εν τέλει θα καταλήξω σε μια κατάσταση όπου ισχύουν τα (Α) και (Β) αλλά δεν υπάρχει ακολουθία θέσεων ώστε να ισχύουν τα (1),(2),(3).

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

Άρα το συνολικό πλήθος καρτών στις θέσεις είναι το πολύ . Αλλά τότε στην θέση υπάρχουν τουλάχιστον κάρτες. Άρα το ζητούμενο αποδείχθηκε.

[ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ]

Όσο για το 2 θέμα, δεν γνωρίζω πως να γράψω την λύση μου σε μορφή latex.Μηπώς μπορεί κάποιος να με βοηθήσει σχετικά με το να βρω κάπου οδηγίες .Ευχαριστώ

[Γιάννης Μπόρμπας]

Γεια σου Ανδρέα, αυτό το λινκ θα σε βοηθήσει:
Latex

[Demetres]

Υπάρχουν επίσης κάποιες λίγο πιο εισαγωγικές οδηγίες εδώ.

Η κύρια διαφορά είναι ότι ο σύνδεσμος του Γιάννη δίνει οδηγίες για γράψιμο σε στον υπολογιστή σου που είναι κάπως πιο δύσκολο στο ξεκίνημα. Από εκείνον τον σύνδεσμο αγνόησε οτιδήποτε μιλάει για packages και \usepackage. Πολλά από αυτά τα «πακέτα» είναι ήδη φορτωμένα στο και δεν χρειάζεται να δηλωθούν περαιτέρω όπως όταν γράφουμε στον υπολογιστή μας.

[ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ]

Ευχαριστώ πολύ Γιάννη και κύριε Δημήτρη

[grigkost]

Όσο για το 2 θέμα, δεν γνωρίζω πως να γράψω την λύση μου σε μορφή latex. Μηπώς μπορεί κάποιος να με βοηθήσει σχετικά με το να βρω κάπου οδηγίες ...

Εκτός των συνδέσμων που ανέφεραν ο Δημήτρης και ο Γιάννης, ένας εύκολος τρόπος για να έχουμε τον κώδικα που θέλουμε είναι με την χρήση του EqEditor. Αυτός εμφανίζεται (σε ξεχωριστό παράθυρο) όταν πατάμε το κουμπί EqEditor που βρίσκεται στην μπάρα του παραθύρου δημοσίευσης.

• Χρησιμοποιώντας τα κατάλληλα κουμπιά του EqEditor στο ορθογώνιο πλαίσιό του εμφανίζεται ο κώδικας ενώ από κάτω εμφανίζεται ο μαθηματικός τύπος που αντιστοιχεί στον κώδικα.
• Όταν γράψουμε τον μαθηματικό τύπο που θέλουμε, αντιγράφουμε τον κώδικα από το ορθογώνιο πλαίσιο και το επικολλούμε στο παράθυρο της δημοσίευσή μας βάζοντάς τον ανάμεσα σε δυο δολλάρια (ή τον επικολλούμε, τον "επιλέγουμε" με το ποντίκι και πατάμε το κουμπί tex).

[ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ]

Αρχικά,έχουμε :

Το οποίο είναι Αδύνατο.Άρα δεν υπάρχει τετραψηφίος που να ικανοποιεί την συγκεκριμένη σχέση.

[Demetres]

Αρχικά,έχουμε :

Το οποίο είναι Αδύνατο.Άρα δεν υπάρχει τετραψηφίος που να ικανοποιεί την συγκεκριμένη σχέση.

Σωστά. Ας γράψουμε όμως περισσότερες λεπτομέρειες για να το δουν και οι υπόλοιποι.

Το



είναι πολλαπλάσιο του και μη αρνητικό. Το είναι μη αρνητικό.

Άρα αναγκαστικά πρέπει



και



Από αυτά είναι τώρα εύκολο να καταλήξουμε στα από την δεύτερη ισότητα, και μετά από την πρώτη.

Άρα η μόνη επιλογή είναι ο αριθμός . Το κατά πόσο είναι επιτρεπτή ή όχι εξαρτάται και από την εκφώνηση. Εφόσον μιλάει για τετραψήφιους, κανονικά πρέπει να την απορρίψουμε.