Πρόβλημα 3o του Διαγωνισμού
Μία επιτροπή από 
κριτικούς κινηματογράφου ψηφίζει για τα Όσκαρ. Κάθε κριτικός ψηφίζει ακριβώς έναν ηθοποιό και ακριβώς μία ηθοποιό.
κριτικούς κινηματογράφου ψηφίζει για τα Όσκαρ. Κάθε κριτικός ψηφίζει ακριβώς έναν ηθοποιό και ακριβώς μία ηθοποιό.
Μετά την ψηφοφορία διαπιστώθηκε ότι για κάθε θετικό ακεραίο 
υπάρχει κάποιος ηθοποιός ή κάποια ηθοποιός που ψηφίστηκε ακριβώς 
φορές. Να αποδείξετε ότι υπάρχουν δύο κριτικοί που ψήφισαν τον ίδιο ηθοποιό και την ίδια ηθοποιό.
υπάρχει κάποιος ηθοποιός ή κάποια ηθοποιός που ψηφίστηκε ακριβώς φορές. Να αποδείξετε ότι υπάρχουν δύο κριτικοί που ψήφισαν τον ίδιο ηθοποιό και την ίδια ηθοποιό.
C2. (Ηνωμένο Βασίλειο)
Ο Ισαάκ και ο Τζέρεμυ παίζουν το ακόλουθο παιχνίδι. Ο Ισαάκ λέει στον Τζέρεμυ ότι σκέφτεται κάποιους $2^{n}$ ακεραίους 
Ο Τζέρεμυ ρωτάει ερωτήσεις της μορφής: "Ισχύει ότι $k_i<k_j$;" στις οποίες ο Ισαάκ απαντά λέγοντας την αλήθεια. Ύστερα από $n2^{n-1}$ ερωτήσεις, ο Τζέρεμυ πρέπει να αποφανθεί αν οι αριθμοί του Ισαάκ είναι όλοι διαφορετικοί μεταξύ τους ή όχι. Να αποδειχθεί ότι ο Τζέρεμυ δεν έχει τρόπο να "είναι σίγουρος" για την τελική του απόφαση.
C3. (Βουλγαρία)
Μία σκακιέρα 
καλύπτεται με ντόμινο 
που μπορούμε να περιστρέφουμε. Δεν ξέρουμε ποια είναι η κάλυψη, αλλά θέλουμε να τη βρούμε. Για το σκοπό αυτό, διαλέγουμε κάποια 
κελιά της σκακιέρας, για τα οποία μαθαίνουμε την θέση των ντόμινο που τα καλύπτουν.
καλύπτεται με ντόμινο που μπορούμε να περιστρέφουμε. Δεν ξέρουμε ποια είναι η κάλυψη, αλλά θέλουμε να τη βρούμε. Για το σκοπό αυτό, διαλέγουμε κάποια κελιά της σκακιέρας, για τα οποία μαθαίνουμε την θέση των ντόμινο που τα καλύπτουν.
Ποιος είναι ο ελάχιστος ώστε ύστερα από την επιλογή των κελιών και μαθαίνοντας τα ντόμινο που τα καλύπτουν, να είμαστε σίγουροι και για όλη την υπόλοιπη κάλυψη;
ώστε ύστερα από την επιλογή των κελιών και μαθαίνοντας τα ντόμινο που τα καλύπτουν, να είμαστε σίγουροι και για όλη την υπόλοιπη κάλυψη;
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου