Διεθνής Μαθηματική Ολυμπιάδα 2015 - Μικρή Λίστα (Συνδυαστική)

C1. Σε μία ευθεία υπάρχουν πόλεις. Κάθε πόλη έχει μία αριστερή μπουλντόζα (στα αριστερά της πόλης και στραμμένη στα αριστερά) και μία δεξιά μπουλντόζα (στα δεξιά της πόλης και στραμμένη στα δεξιά). Όλες οι μπουλντόζες έχουν διαφορετικά μεγέθη.
Οι μπουλντόζες ξεκινάνε να κινούνται προς την κατεύθυνσή της η καθεμιά και όταν μία δεξιά μπουλντόζα συναντήσει μία αριστερή, τότε η μεγαλύτερη βγάζει τη μικρότερη εκτός δρόμου (όπου και παραμένει αυτή εκεί).

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

Έστω τώρα δύο πόλεις και με την να είναι δεξιά της . Θα λέμε ότι η πόλη εξοβελίζει την πόλη αν η δεξιά μπουλντόζα της μπορεί να φτάσει στην πόλη βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά. Όμοια, θα λέμε ότι η πόλη εξοβελίζει την πόλη αν αριστερή μπουλντόζα της μπορεί να φτάσει στην πόλη βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά. 

Να αποδείξετε ότι υπάρχει ακριβώς μία πόλη που δεν μπορεί να εξοβελιστεί από καμιά άλλη. 

C2. Περσινό πρώτο θέμα της ΙΜΟ. 

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

C4. Έστω ένας θετικός ακέραιος. Οι παίκτες και παίζουν εναλλάξ ένα παιχνίδι, διαλέγοντας κάθε φορά έναν θετικό ακέραιο . 

Οι κανόνες είναι οι ακόλουθοι:

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

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

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

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

C5. Περσινό 6ο θέμα της ΙΜΟ. 

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

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

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

Πηγή