SNS Pisa 2018 Problema 3

Scuola Normale Superiore, Sant'Anna, Indam, etc. Cosa studiare, come prepararsi.
Rispondi
nicarepo
Messaggi: 29
Iscritto il: 23 lug 2018, 09:20

SNS Pisa 2018 Problema 3

Messaggio da nicarepo »

Sono disposte coperte in fila su un tavolo $ n $ carte, ognuna con un valore da $ 1 $ a $ n $. Una carta è vincente se le due carte adiacenti hanno un valore minore della prima (o la carta adiacente se ci si trova ai bordi). Dimostrare che scoprendo una a una le carte è possibile individuare una carta vincente con al più $ 1+2log_2 (n) $

Io ho risolto il problema per induzione e mi sembrava un metodo abbastanza logico, ma uscendo ho sentito che si trattava di un problema classico secondo cui la scelta corretta era quella di scegliere ai bordi e dimezzare via via.
Secondo voi potrebbero contarmelo corretto?
Schrodingers_Bat
Messaggi: 26
Iscritto il: 26 ago 2018, 09:57

Re: SNS Pisa 2018 Problema 3

Messaggio da Schrodingers_Bat »

Dipende che cosa intendi per induzione. come l'hai fatto?
P=NP
Schrodingers_Bat
Messaggi: 26
Iscritto il: 26 ago 2018, 09:57

Re: SNS Pisa 2018 Problema 3

Messaggio da Schrodingers_Bat »

appena ho un attimo di tempo ti dico come l'ho risolto io
P=NP
nicarepo
Messaggi: 29
Iscritto il: 23 lug 2018, 09:20

Re: SNS Pisa 2018 Problema 3

Messaggio da nicarepo »

Allora, è evidente per 1,2 e 3. Si suppone vero per n, e si dimostra per n+1, aggiungendo una carta in un punto a caso del mazzo già disposto a terra.
Schrodingers_Bat
Messaggi: 26
Iscritto il: 26 ago 2018, 09:57

Re: SNS Pisa 2018 Problema 3

Messaggio da Schrodingers_Bat »

aspetta tu sei Leonardo dell'aula 6? Nel qual caso mi sa di averti già detto perché non funziona. Altrimenti spiegami un attimo cosa hai pensato.

Comunque, la risoluzione che ho dato io è la seguente, che dovrebbe avere senso (ma chiedo conferma). prendi le due carte centrali del mazzo (o la centrale e una delle due affianco, se n è dispari). una delle due è maggiore dell'altra. traccia una "freccia" che va dalla minore alla maggiore. La freccia ti indica una delle due metà in cui è stato diviso l'intervallo. prendi le due carte centrali di quell'intervallo, traccia una freccia e continua così. praticamente continui a ottenere un intervallo compreso tra due frecce, cioè tali che le carte note che lo delimitano sono maggiori di quelle accanto.
Prima o poi ottieni una delle due situazioni seguenti:
- una freccia punta contro l'esterno della fila, cioè una carta esterna è maggiore di quella interna. allora la carta esterna è vincente.
- continui a dimezzare l'intervallo fino a che non ottieni una carta compresa tra due frecce. in questo caso, se la carta centrale è maggiore delle due carte a lato essa è vincente; se è minore di entrambe, sono entrambe vincenti (perché, essendo delle frecce, l'altra carta che hanno a lato è minore); se è compresa tra una e l'altra, la carta maggiore tra le due è vincente, per lo stesso motivo.

Quante carte hai scoperto al massimo? 1 (la carta finale)+2log2(n) (perché log2(n) indica quante volte si può dimezzare n, e ogni volta che dimezzi peschi 2 carte).
QED
P=NP
nicarepo
Messaggi: 29
Iscritto il: 23 lug 2018, 09:20

Re: SNS Pisa 2018 Problema 3

Messaggio da nicarepo »

Ciao! Ahahaha cercavo altri pareri, comunque ho capito questa soluzione, ma non perché l’induzione non funziona...
Schrodingers_Bat
Messaggi: 26
Iscritto il: 26 ago 2018, 09:57

Re: SNS Pisa 2018 Problema 3

Messaggio da Schrodingers_Bat »

Perché, se ti fai un po' di casi, vedi che se ne peschi a caso quante ne chiede il testo non è detto che trovi una vincente (esempio: se le metti tutte in ordine crescente e le peschi una alla volta trovi una carta vincente solo alla fine). Allora, anche se per induzione dimostri che le vincenti aumentano o al massimo rimangono uguali, non è detto che ti bastino quelle mosse per pescarne a caso una. Il nocciolo dell'esercizio era trovare un procedimento, sempre uguale per qualsiasi n e per qualsiasi disposizione di carte, tale che tu possa essere sicuro al 100% di trovare una vincente dopo tot mosse.

E poi, che sia vero per 2 e 3 è un po' generico. Ok, 2log2(2)=2, 2log2(3)+1$ \ge $3. Però potrebbe essere tranquillamente che devi pescarne al massimo n, o (invento) che devi pescarne al massimo n/2+2. Da questi casi non hai ricavato una formula precisa che ti dica che devi pescarne esattamente 1+2log2(n)
P=NP
nicarepo
Messaggi: 29
Iscritto il: 23 lug 2018, 09:20

Re: SNS Pisa 2018 Problema 3

Messaggio da nicarepo »

Infatti il testo non chiede di ricavare quella formula, ma solo di verificare che funzioni, e per induzione non dimostro che il numero di vincenti cambia o meno, ma che quella formula continua a funzionare... in ogni caso la tua soluzione è indubbiamente corretta e attinente alla richiesta. Lo stesso discorso vale per il primo esercizio, il testo chiedeva di trovare il numero di monete, non di dimostrare il perché di quel numero. Di certo, però, se hai dimostrato il perché terranno un occhio di riguardo
Schrodingers_Bat
Messaggi: 26
Iscritto il: 26 ago 2018, 09:57

Re: SNS Pisa 2018 Problema 3

Messaggio da Schrodingers_Bat »

Che poi, anche lì, se trovavi quante monete erano non avevi dimostrato che non ci fossero altri casi.

Dai, speriamo te la contino buona.
P=NP
Rispondi