Η Άννα και η μετάθεση

[DrStrange]

Η Άννα σκέφτεται μια μετάθεση του όπου δεδομένος θετικός ακέραιος τον οποίο και γνωρίζετε. Θέλετε να την μαντέψετε. Έτσι, κάνετε ερωτήσεις όπου της δίνετε διαφορετικούς δείκτες και σας λέει το . Μπορείτε να μαντέψετε την μετάθεση κάνοντας το πολύ ερωτήσεις?

[ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ]

Η Άννα σκέφτεται μια μετάθεση του όπου δεδομένος θετικός ακέραιος τον οποίο και γνωρίζετε. Θέλετε να την μαντέψετε. Έτσι, κάνετε ερωτήσεις όπου της δίνετε διαφορετικούς δείκτες και σας λέει το . Μπορείτε να μαντέψετε την μετάθεση κάνοντας το πολύ ερωτήσεις?

Θα αποδείξω πως είναι εφικτό.
Ξεκινάμε δίνοντας τους δείκτες και μετά οπότε γνωρίζουμε τα και .
Γράφουμε και , είναι και .
Δεν μπορεί ταυτόχρονα αφού τότε , αδύνατο.
Αν μας δώσει τότε δεν θα μπορούσε να είναι αφού τότε .
Άρα καταλαβαίνουμε πως .
Όμοια αν μας δώσει καταλαβαίνουμε ότι .
Επίσης δεν υπάρχει περίπτωση να μας δώσει αφού αν π.χ τότε αδύνατο.
Οπότε με δύο ερωτήσεις έχουμε διατάξει τα .
Κάνοντας την ίδια διαδικασία για τα αν πάρουμε συνεχίζουμε με τα .
Αν τότε επειδή γνωρίζουμε τα μπορούμε να διατάξουμε και τα .
Συνεχίζοντας τον αλγόριθμο μέχρι το και με σύνολο ερωτήσεις έχουμε διατάξει όλα τα και έτσι βρήκαμε την μετάθεση!

[2nisic]

Έστω δύο αριθμοί.
Θα δείξουμε ότι με δύο ερώτησης μπορούμε να βρούμε έναν από τους δύο.

Ρωτάμε τούς και τότε έχουμε:




Θα δείξουμε ότι αν τότε.

Αν τότε .

Αν τότε αλλά δηλαδή άτοπο αφού εμείς ξέρουμε ότι .


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


Edit:Με πρόλαβε ο πρόδρομος!

[2nisic]

Η Άννα σκέφτεται μια μετάθεση του όπου δεδομένος θετικός ακέραιος τον οποίο και γνωρίζετε. Θέλετε να την μαντέψετε. Έτσι, κάνετε ερωτήσεις όπου της δίνετε διαφορετικούς δείκτες και σας λέει το .Να αποδειχθεί ότι με :
Αν με ερωτήσεις
Αν με ερωτήσεις μπορούμε να βρούμε την μετάθεση της Άννας.