Quizzino della domenica: palline da ping pong

In Matelandia, come ben sapete, tantissimi oggetti iperuranici sono presenti in quantità infinita. Tra questi oggetti con disponibilità a piacere ci sono delle palline da ping pong con impresso un numero intero positivo, da #1 in su. (Nel caso vi chiedeste come mai c’è anche un cancelletto, è perché era il modo più semplice per distinguere il 6 dal 9. Il cancelletto si mette sempre prima del numero). Supponete ora di prendere un numero finito di palline, numerate come volete, e metterle in un contenitore parecchio ampio. A ogni mossa prendete a caso una pallina, guardate il numero che ha, la togliete e aggiungete un numero qualunque (finito) di palline, con l’unica regola che il numero presente su queste palline deve essere strettamente minore di quello della pallina tolta. Questo significa che se estraete una pallina #1 non potete aggiungerne nessuna, ma con una pallina #666 potete rimetterne un milione di #42, e magari un paio di #314 così per sport. Dimostrate che prima o poi svuoterete il contenitore.

[pallina]

(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p417.html; la risposta verrà postata lì il prossimo mercoledì. Problema di Raymond Smullyan)

6 comments

  1. forse non ho capito bene . Innanzitutto, si considera implicito che il giocatore cerca di vuotare il secchio? o la cosa deve essere dimostrata a prescindere dalla strategia?
    Nel primo caso, dopo ogni estrazione di un numero superiore a 1, introdurrei qualche pallina con sopra “1”.
    Dato che il numero di palline in partenza è finito, anche il sottoinsieme di quelle maggiori di 1, è finito. Se non introduco mai palline con valore superiore a 1, e quelle che vengono estratte non vengono sostituite, prima o poi resteranno solo le “1” che saranno comunque un numero finito, per vincolo esplicito.

    • Devi dimostrare che il giocatore non può non riuscire a svuotare il contenitore qualunque strategia scelga.

  2. ogni volta che viene estratta una pallina con #numero_massimale, numero_massimale diminuisce, o, nel peggiore dei casi, diminuisce il numero di palline con #numero_massimale…

  3. Immagino , per stabilità architettonica che le palline siano cubiche, e le dispongo a strati con i numeri più alti in alto, e tutti numeri uguali alla stessa altezza. Ogni volta che estraggo un numero superiore a 1 (invece di rimestare nel secchio, occorrerà un marchingegno random), aggiungo un cubetto, o dieci, o un milione di cubetti, al piano subito inferiore. (si tratta della strategia più punitiva, mentre quella di inserire un solo 1 è la più favorevole) La montagna , via via, andrà allargandosi a vari livelli, mentre perderà (pochi ma inesorabilmente) cubetti per definizione posti più in alto di quelli aggiunti. Trattandosi di quantità finite, non dobbiamo impaurirci se alcuni livelli diventano ingombranti; prima o poi ogni cubetto di quel livello verrà estratto, e sostituito da materiale situato più in basso. Un meccanismo lento, ma inesorabile. So che questa “dimostrazione” non è rigorosa, ma mi convince

  4. Premetto che il messaggio potrebbe risultare alquanto palloso, non è indispensabile leggerlo tutto.

    Sono d’accordo che le azioni per svuotare il contenitore siano in ogni caso un numero finito, ma ho dei dubbi sul fatto che “prima o poi svuoterete il contenitore”, senza aiuti.

    Ho provato (scrivendomi gli appunti su una bozza di mail, così da poterli avere sott’occhio nei vari minuti di attesa, ed è per quello che ci ho messo tanto) considerando un contenitore dove inizialmente sono inserite 4 palle, contrassegnate una per una da #1 a #4 (no, avevo pensato anche al milione di palle, però quattro bastano, come inizio), ed ogni volta che viene estratta una palla si legge il valore indicato e se questo è (#1) ci si limita ad estrarre un’altra palla, altrimenti se ne inseriscono altre 4, nello stesso contenitore, tutte uguali tra loro e del valore immediatamente inferiore; se non ci sono più palle, finisce lì.

    Riepilogando: si estrae una palla per volta, se esce (#1) non si inserisce nulla, se esce (#V) si inseriscono sempre N palle contrassegnate (#V-1), poi si ricomincia finché restano palle; senza più palle stop.

    Prima ipotesi, abbiamo un contenitore magico che fa affiorare immediatamente i numeri più alti (qualcosa che ci assomiglia molto esiste da decenni e funziona benissimo se le palle hanno un peso complementare al valore visibile, i valori più bassi sulle palle più pesanti, quello non è un problema) *

    Seconda ipotesi, abbiamo già tutte le palle numerate, in giusta quantità, in modo da non perdere tempo con i rabbocchi.

    * dopo un paio di tentativi veloci con valori bassi, pare confermato che, con le regole adottate, funziona lo stesso anche con estrazioni assolutamente casuali.

    E partiamo con la rappresentazione: dalla situazione iniziale
    (#4), (#3), (#2), (#1)
    dapprima si elimina il (#4) in 1 mossa, ottenendo
    (4+1) palle (#3) e le singole palle (#2), (#1);
    quindi si elimina il (#3) in 5 mosse, ottenendo
    ((4+1)*4+1) palle (#2) e la singola palla (#1);
    quindi si elimina il (#2) in 21 mosse, ottenendo
    (((4+1)*4+1)*4+1) palle (#1) e poi basta,
    che si eliminano in 85 mosse.

    In tutto, le mosse di prelievo sono
    (4-3)*(4^3)+(4-2)*(4^2)+(4-1)*(4^1)+(4-0)*(4^0)
    = 112 (sì, ci sono più parentesi del necessario e si potrebbe semplificare, ma così è più facile generalizzare il calcolo).

    Se al posto di sole 4 palle si decide di metterne 10, contrassegnandole di conseguenza da (#1) a (#10) e aggiungendo all’occorrenza sempre 10 palle seguendo la medesima regola, si dovrebbe calcolare
    1*10^9+2*10^8+3*10^7+4*10^6+5*10^5+6*10^+7*10^3+8*10^2+9*10+10
    = 1234567900 (un miliardo e oltre).
    Un secondo per ogni mossa, senza tener conto del tempo impiegato per aggiungerle quando serve, sono più di 39 anni.
    Pieni, senza perdere un colpo e senza fare altro, *assolutamente* *niente* *altro* …

    Se con lo stesso procedimento si pensasse a 16 palle, l’ordine di grandezza supera l’età stimata dell’universo, in secondi, quindi continuo ad avere qualche dubbio che si riesca a svuotare il contenitore, sempre ed in ogni caso, in tempi ragionevoli :-)