Interrogazione

[axpgn]

Un gruppo di $20$ studenti è in fila per sostenere un esame orale dal Prof.Tiffi.
Però nessuno osa entrare
Decidono allora di fare una lotteria, scrivono i numeri da $1$ a $20$ su dei foglietti di carta, li mettono in un cappello e ciascuno ne estrae uno; chi prende il numero $1$ entra.
E ripetono poi lo stesso schema numerando i bigliettini da $1$ a $19$ e poi da $1$ a $18$ e così via per venti volte: chi prende l'uno entra.
Sorprendentemente nessuno studente estrae due volte lo stesso numero.

Clara pesca il $14$ alla prima estrazione: quanti studenti sono entrati prima di lei?


Cordialmente, Alex

[Quinzio]

Forse e' troppo semplice, ma...

facciamo che ci sia un osservatore che prende nota del turno a cui entra uno studente, quindi lo studente che entra al quinto turno avra' l'etichetta $5$, e poi prende nota dei bigliettini che ogni studente estrae.
L'unica soluzione possibile e' che lo studente $n$ al primo turno estrae il biglietto $n$, al secondo turno (se non e' gia' entrato) estrae $n-1$, al terzo turno, se non e' gia' entrato estrae $n-2$ e cosi' via.
Per essere ancora piu' chiari, l'ultimo studente ad entrare estrae $20$, poi $19$, poi $18$ fino a che rimane solo lui ed estrae per forza $1$.
Quindi Clara ha $13$ studenti prima di lei.

[axpgn]

Giusto, molto bene


Però ...

... non c'è la dimostrazione del fatto che sia "l'unica soluzione possibile" o almeno non mi è chiara ... IMHO

[Quinzio]

"axpgn":Giusto, molto bene


Però ...

... non c'è la dimostrazione del fatto che sia "l'unica soluzione possibile" o almeno non mi è chiara ... IMHO

No, non c'e' proprio.

[axpgn]

[Quinzio]

Dimostrazione:

dobbiamo riempire una matrice triangolare superiore con 20 bigliettini con scritto "1", 19 con scritto "2", ..., 1 con scritto "20".
Non ci devono essere 2 numeri uguali sulla stessa riga o sulla stessa colonna.
Iniziamo con gli "1".
Siccome abbiamo 20 bigliettini e 20 colonne, ogni colonna deve avere un bigliettino (pigeon hole).
La colonna 1 ha solo una riga e quindi un bigliettino "1" va nella casella (1,1).
Nella riga 1 non si possono piu' mettere bigliettini "1" e quindi rimaniamo con una matrice triangolare 19x19 e 19 bigliettini.
Per lo stesso ragionamento di prima un bigliettino lo dobbiamo mettere in (2,2).
Rimaniamo con una matrice triangolare 18x18 e il terzo bigliettino lo mettiamo in (3,3).
E cosi' via.
Poi abbiamo 19 bigliettini con scritto "2" e una matrice triangolare 19x19.
Con lo stesso ragionamento collochiamo tutti i bigliettini "2" e quindi tutti gli altri bigliettini fino al "20" in posizione (1,20).

[axpgn]

... mmm ...

Non vedo però come questa costruzione dimostri che chi ha preso il $14$ alla prima estrazione entri poi per quattordicesimo ... non vedo il collegamento ...
Io l'ho dimostrato per induzione ... credo

[Benihime1]

- 20-esimo turno di pescata: c'è solo l'ultimo studente in ordine di entrata, e pesca "1".
- 19-esimo turno di pescata: ci sono l'ultimo studente e il penultimo, e devono aver pescato rispettivamente "2" e "1"
- 18-esimo turno di pescata: ci sono l'ultimo, il penultimo e il 18-esimo in ordine di entrata; il 18-esimo pesca "1" per definizione, ultimo pesca "3" (non può pescare "1" e "2" perché li pescherà ai turni successivi e ciascuno studente non pesca mai due volte lo stesso biglietto) e penultimo pesca "2"
- 17-esimo turno di pescata: ci sono l'ultimo, il penultimo, 18-esimo e 17-esimo in ordine di entrata; il 17-esimo pesca "1", ultimo pesca "4" (stesso ragionamento di cui sopra), penultimo pesca "3" (perché pescherà "1" e "2" in futuro), e 18-esimo pesca "2"
Proseguendo così risulta che al turno di pescata $k$, lo studente $s$-esimo per ordine di entrata pesca il $(s-k+1)$-biglietto; quindi se Clara per $k=1$ ha avuto $(s-k+1)=14$ deve essere che $s=14$: è entrata per 14esima