I Giochi del Lunedì di Prisma del 24 marzo 2025 a cura di Fabio Ciuffoli
Oggi presentiamo 4 problemi utilizzati come punto di partenza per i colloqui di lavoro a Paypal, la società di pagamenti on line fondata e gestita da Elon Musk, Peter Thiel e David Sacks, a Palo Alto nel 2000. I tre sono diventati famosi per la loro ingegnosità imprenditoriale, i miliardi accumulati, la vita stravagante, la politica di destra trumpista e forse non a caso la rivista Fortune nel 2007 li definì The Paypal Mafia. In ogni caso nella loro storia c’è un’interessante passione per i puzzle logici e matematici. Invitiamo i lettori a inviarci considerazioni, osservazioni e proposte di soluzione utilizzando lo spazio riservato ai commenti. Domani pomeriggio alle 17.00 pubblicheremo le soluzioni.
Colloquio per Paypal
1. Due corde. Ci sono due corde, ogni corda ha una densità variabile nella sua lunghezza in modo che brucia a una velocità diversa dall’altra, ma ciascuna impiega un’ora per bruciare completamente. Come utilizzeresti le due corde per misurare 45 minuti?
2. Dividi e conquista. I numeri interi possono avere un numero dispari di divisori o un numero pari. Ad esempio i divisori di 4 sono 1, 2 e 4, per cui 4 ha tre divisori, quindi un numero dispari di divisori; i divisori di 24 sono 1, 2, 3, 4, 6, 8, 12 e 24, sono otto divisorii e perciò 24 ha un numero pari di divisori. Quali numeri interi hanno un numero dispari di divisori?
3. Enigma delle monete. C’è un tavolo circolare di diametro non specificato. Tu e il tuo avversario avete una notevole scorta di monete di dimensioni identiche. Il gioco prevede che ognuno a turno, metta una moneta sul tavolo. Nessuna moneta può essere spostata dopo il posizionamento e nessuna moneta può essere posizionata interamente o parzialmente sopra un’altra. Il primo giocatore che non riesce a piazzare una moneta perde. Puoi scegliere se iniziare per primo o per secondo. Qual è la tua strategia per assicurarti la vittoria?
4. I lampioni. In una strada ci sono 100 lampioni, ciascuno regolato da un suo interruttore. Sono tutti spenti, quando passa di lì un bambino che schiaccia tutti gli interruttori e così li accende tutti. Dopo di lui passa un secondo bambino che schiaccia gli interruttori della tabellina del 2 e spegne tutti quelli che tocca. Un terzo bambino schiaccia gli interruttori della tabellina del 3 e in questo modo spegne alcuni lampioni e ne accende altri. Un quarto bambino cambia di segno agli interruttori della tabellina del quattro e così via fino all’ultimo bambino. Dopo che è passato il centesimo bambino, quali lampioni saranno accesi? E c’è una regola in generale?
Aggiornamento per le soluzioni click qui.
I primi tre problemi sono tratti da The Founders – La storia di Paypal e degli imprenditori che hanno plasmato la Silicon Valley – di Jimmy Soni. Un libro sulla Paypal Mafia.
18 risposte
3 – Enigma delle monete. Parto per primo e piazzo una moneta al centro. Dopodiché, ogni moneta che piazzerò sarà simmetrica rispetto a quella dell’altro giocatore. Così facendo io ho la garanzia che dopo la mia giocata il sistema goda di simmetria centrale. Se il mio avversario riesce a piazzare una moneta in un punto io la posso piazzare nel punto diametralmente opposto, garantendomi sempre una mossa.
Ho trovato che l’impaccamento ottimo di cerchi piccoli entro un cerchio più grande prevede sempre un numero dispari di cerchi piccoli (vedi figura) . Se fosse garantito l’impaccamento ottimo dovrei giocare per primo.
Risposta a
“Vic ha detto:
25 Marzo 2025 alle 15:06
Ah beh! La situazione allora si fa più articolata 🙂
A naso mi veniva da rispondere che la soluzione sarà duale del caso precedente, cioè NON devono passare i bambini contrassegnati con i numeri quadrati perfetti.
Ho però provato ad abbozzare (mentalmente) i primi passaggi, e ho scoperto che se non passa il #4, non deve passare nemmeno il #8 (pur non essendo un quadrato), e nemmeno il #12 (perché sono passati: il #2 ON; il #3 OFF; il #6 ON), affinché i rispettivi lampioni rimangano accesi.
Potrei allora dedurre che:
Devono essere esclusi i numeri quadrati perfetti e i loro multipli.”
Ottimo, ho inserito la soluzione a questo problema tra le altre soluzioni pubblicate nel pomeriggio di oggi all’apposito link. Mi è sembrato un interessante problema con una bella soluzione.
Ancora per Vic. Va anche detto che, nella sua prima formulazione, il problema non era chiarissimo.
Per le corde farei così. Accenderei i due capi della prima carda ed un capo della seconda. Dopo mezz’ora la prima corda sarà bruciata tutta,, la parte restante della seconda va accesa anche all’ altro capo. Quando finisce di bruciare sono passati 45 minuti
Ottimo, nel pomeriggio tutte le soluzioni commentate.
3. Inizio per primo, posiziono al centro, ad ogni mossa del mio avversario, posiziono la moneta in modo simmetrico, così lascio sempre una situazione simmetrica e riesco a vincere posizionando + monete..
Quesito 4.
Questo problema si può intendere come un’applicazione del Quesito 2.
Un lampione resterà acceso solo se verrà toccato da un numero dispari di ragazzi, cioè se ha un numero dispari di divisori.
E abbiamo visto che questo succede per i numeri quadrati perfetti.
Quindi la risposta è:
Dopo 100 bambini rimarranno accesi 10 lampioni (i quadrati perfetti minori di 100).
Questa è anche la regola generale.
Ottimo, che ne dici della variante del problema suggerito da Fabio DF?
Riguardo la variante di Fabio DF al Quesito 4, forse mi è sfuggito qualcosa…
Se le regole sono esattamente quelle descritte nel testo, in particolare lampioni inizialmente tutti spenti, allora passa il primo bambino e li accende tutti.
Basterebbe solo fermarsi qui ed è risolto: lampioni tutti accesi.
In più mi sembra che questa sia condizione non solo sufficiente, ma necessaria!
Affinché il lampione #2 resti acceso, NON deve passare il bimbo #2;
e idem vale per il #3;
lo stesso anche per il #4: dato che non è passato il #2, se passasse ora il bimbo #4, spegnerebbe il lampione, e nessun altro in seguito potrebbe riaccenderlo;
e così via per tutti gli altri.
Quindi deve passare solo il bimbo #1 e stop.
Per una miglior comprensione riporto il testo originale suggerito da Fabio DF: “Supponiamo che ci siano 1000 lampioni numerati da 1 a 1000.
Tutti i lampioni, tranne il primo, sono spenti. Ci sono anche 999 (da 2 a 1000) bambini ognuno dei quali gioca con i lampioni nel seguente modo:
– il bambino 2 preme l’interruttore sul lampione 2 e, di conseguenza, cambia lo stato del lampione 2 e di tutti i suoi multipli
– il bambino 3 preme l’interruttore sul lampione 3 e, di conseguenza, cambia lo stato del lampione 3 e di tutti i suoi multipli
e così via fino al 999.
Ora, se volessimo accendere tutti i lampioni, quali bambini sarebbe necessario far giocare?
P.S. ovviamente, il bambino 1 non può far parte del gioco altrimenti sarebbe stato banale.
Ah beh! La situazione allora si fa più articolata 🙂
A naso mi veniva da rispondere che la soluzione sarà duale del caso precedente, cioè NON devono passare i bambini contrassegnati con i numeri quadrati perfetti.
Ho però provato ad abbozzare (mentalmente) i primi passaggi, e ho scoperto che se non passa il #4, non deve passare nemmeno il #8 (pur non essendo un quadrato), e nemmeno il #12 (perché sono passati: il #2 ON; il #3 OFF; il #6 ON), affinché i rispettivi lampioni rimangano accesi.
Potrei allora dedurre che:
Devono essere esclusi i numeri quadrati perfetti e i loro multipli.
Sul problema 4. E’ un quesito che conosco piuttosto bene. Ne conosco una variante interessante.
Invece di far passare tutti i bambini e capire quali sono i lampioni che rimangono accesi, con le stesse regole, si chiede quali siano i bambini che devono essere fatti passare affinchè tutti i lampioni risultino accesi.
2. I numeri che hanno un numero dispari di divisori sono i quadrati perfetti. Un numero n può essere scomposto in fattori primi in questo modo:
n=(p1^a1)*(p1^a2)*…*(pm^am)
Il numero di divisori di n sarà dato dal prodotto dei singoli esponenti dei primi della fattorizzazione aumentati di 1. Cioè:
d(n) = (a1+1)*(a2+1)*…*(am+1)
Affinchè d(n) sia dispari, sarà, quindi, necessario che tutti i fattori di d(n) siano dispari, ossia che tutti gli ai siano pari, Il che si ha se e soltanto se n è un quadrato perfetto.
Quesito 2.
I numeri che hanno un numero dispari di divisori sono tutti e soli i quadrati perfetti (1, 4, 9, 16,…).
Pensando infatti ai divisori di un numero N come lati di un rettangolo, il loro prodotto (presi a due a due) da l’area N del rettangolo.
Solo se N è un numero quadrato prefetto, tra i rettangoli di area N ci sarà anche un quadrato di lato k (k*k=N).
Il numero k, divisore di N, rompe la parità degli altri divisori, che sono sempre a coppie (=di lati), in quanto k si utilizza 2 volte per ottenere l’area N.
A me è venuta in mente questa analogia “geometrica” per spiegare la risposta.
Ottima analogia “geometrico visiva”, non ci avevo pensato… A domani per le soluzioni.
1. Si accende la prima da ambo le parti, e la seconda da una parte… La prima dopo mezz’ora sarà completamente consumata, si accende la seconda dall’altra parte che brucerà in 1/4 d’ora
t1 = t0 + t15′
2. Come il quiz 4 delle lampadine V 100 = 10 restano accese…
Quadrati perfetti 4-9-16-25- 36…ecc.