EGMO 2018/3

#1

Οι

διαγωνιζόμενες σε μία EGMO, ονομάζονται $C_1,C_2,\ldots,C_n$ . Μετά το διαγωνισμό μπαίνουν στην ουρά η μια πίσω από την άλλη, έξω από το εστιατόριο σύμφωνα με τους ακόλουθους κανόνες.

$\bullet$ Το συμβούλιο των Κριτών επιλέγει μια αρχική διάταξη των διαγωνιζομένων στην ουρά.
$\bullet$ Κάθε λεπτό το συμβούλιο επιλέγει έναν ακέραιο

με $1 \leqslant i \leqslant n$ .
- Αν η διαγωνιζόμενη C_i

έχει μπροστά της τουλάχιστον

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

θέσεις.
- Αν η διαγωνιζόμενη C_i

έχει μπροστά της λιγότερες από

σε πλήθος άλλες διαγωνιζόμενες, τότε το εστιατόριο ανοίγει και η διαδικασία τερματίζεται.

(α) Αποδείξτε πως, ανεξαρτήτως των επιλογών του Συμβουλίου των Κριτών, η διαδικασία δεν μπορεί να συνεχίζεται επ’ άπειρον.
(β) Για κάθε

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

).

#2

Ας γράψω

για τον μέγιστο αριθμό φορών που μπορεί επιτροπή να επιλέξει το

και η

να μετακινηθεί μπροστά.

Παρατηρούμε ότι όταν γίνεται αυτό, η C_k

έχει μπροστά της τουλάχιστον

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

με

.

Όμως η κοπέλα C_k

μπορεί να περάσει την κοπέλα C_i

το πολύ

φορές. (Μία αν ξεκίνησε πιο πίσω, και ακόμη μία για κάθε φορά που η C_i

περνά την

.)

Πρέπει λοιπόν f(n) = 0

και $f(k) \leqslant (f(k+1)+1) + ((f(k+2)+1) + \cdots + (f(n)+1)$ .

Επαγωγικά τώρα είναι απλό ότι $f(n-r) \leqslant 2^{r} - 1$ . (Με επαγωγή στο

.)

Άρα θα γίνουν το πολύ $f(1) + \cdots + f(n) \leqslant 2^{n}-n-1$ προσπεράσματα.

Αυτό μπορεί να επιτευχθεί ως εξής:

Ξεκινάμε από την διάταξη $n,n-1,\ldots,1$ . Επαγωγικά (οι περιπτώσεις n=1,2

είναι προφανείς) μπορούμε να καταλήξουμε στην $n,1,2,\ldots,n-1$ κάνοντας $2^{n-1}-n$ προσπεράσματα. Μετά επιλέγουμε διαδοχικά τους $1,2,\ldots,n-1$ για να καταλήξουμε στην διάταξη $n-1,n-2,\ldots,1,n$ . Μετά μπορούμε να κάνουμε επαγωγικά άλλες $2^{n-1}-n$ κινήσεις.

Συνολικά καταφέραμε να κάνουμε $2(2^{n-1}-n)+(n-1) = 2^n - n - 1$ κινήσεις.

Άρα το μέγιστο ποσό που μπορούν να πάρουν οι κριτές είναι 2^n-n-1

ευρώ.

EGMO 2018/3

EGMO 2018/3

Re: EGMO 2018/1/3

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