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

DrStrange · #1

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

του

όπου

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

διαφορετικούς δείκτες i,j

και σας λέει το $p_i \mod p_j$ . Μπορείτε να μαντέψετε την μετάθεση κάνοντας το πολύ $2 \cdot n-2$ ερωτήσεις?

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #2

DrStrange έγραψε: ↑
Σάβ Μάιος 01, 2021 7:40 pm
Η Άννα σκέφτεται μια μετάθεση του όπου δεδομένος θετικός ακέραιος τον οποίο και γνωρίζετε. Θέλετε να την μαντέψετε. Έτσι, κάνετε ερωτήσεις όπου της δίνετε διαφορετικούς δείκτες και σας λέει το $p_i \mod p_j$ . Μπορείτε να μαντέψετε την μετάθεση κάνοντας το πολύ $2 \cdot n-2$ ερωτήσεις?

Θα αποδείξω πως είναι εφικτό.
Ξεκινάμε δίνοντας τους δείκτες 1,2

και μετά

οπότε γνωρίζουμε τα $u_1=p_1 \pmod {p_2}$ και $u_2=p_2\pmod{p_1}$ .
Γράφουμε p_1=ap_2+u_1

και

, είναι $0\leq u_1\leq p_2-1$ και $0\leq u_2\leq p_1-1$ .
Δεν μπορεί $a,b\neq 0$ ταυτόχρονα αφού τότε p_1>p_2>p_1

, αδύνατο.
Αν μας δώσει u_1<u_2

τότε δεν θα μπορούσε να είναι a=0

αφού τότε $u_2\leq p_1-1=u_1-1<u_2-1$ .
Άρα καταλαβαίνουμε πως p_1>p_2

.
Όμοια αν μας δώσει u_2>u_1

καταλαβαίνουμε ότι p_1<p_2

.
Επίσης δεν υπάρχει περίπτωση να μας δώσει u_1=u_2

αφού αν π.χ a=0

τότε $u_2\leq p_1-1=u_1-1=u_2-1$ αδύνατο.
Οπότε με δύο ερωτήσεις έχουμε διατάξει τα p_1,p_2

.
Κάνοντας την ίδια διαδικασία για τα p_2,p_3

αν πάρουμε p_3>p_2

συνεχίζουμε με τα p_3,p_4

.
Αν

τότε επειδή γνωρίζουμε τα $p_1,p_3\pmod{p_2}$ μπορούμε να διατάξουμε και τα p_1,p_3

.
Συνεχίζοντας τον αλγόριθμο μέχρι το p_n

και με σύνολο 2(n-1)=2n-2

ερωτήσεις έχουμε διατάξει όλα τα p_i

και έτσι βρήκαμε την μετάθεση!

2nisic · #3

Έστω

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

Ρωτάμε τούς p1,p2

και

τότε έχουμε:

$p1\equiv x1(mod p2)$
$p2\equiv x2(mod p1)$

Θα δείξουμε ότι αν x1>x2

τότε

.

Αν

τότε

.

Αν

τότε

αλλά

δηλαδή

άτοπο αφού εμείς ξέρουμε ότι x1>x2

.

Άρα με 2(n-1)

ερώτησης έχουμε βρει n-1

αριθμούς και ο τελευταίος είναι αυτός που λείπει.

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

2nisic · #4

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

του

όπου

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

διαφορετικούς δείκτες i,j

και σας λέει το $p_i \mod p_j$ .Να αποδειχθεί ότι με :
Αν n=2k

με

ερωτήσεις
Αν n=2k+1

με

ερωτήσεις μπορούμε να βρούμε την μετάθεση της Άννας.

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

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

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

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

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

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