Dalle Nazionali del Belgio di quest'anno:
Elfs and trolls are seated at a round table, 60 creatures in total. Trolls always lie, and all elfs always speak the truth, except when they make a little mistake.
Everybody claims to sit between an elf and a troll, but exactly two elfs made a mistake! How many trolls are there at this table?
Trad:
Elfi e Troll sono seduti attorno a un tavolo rotondo, 60 creature in totale. I Troll mentono sempre e gli Elfi dicono sempre la verità, tranne quando fanno un piccolo errore. Ognuno dichiara di sedere tra un Elfo e un Troll, ma esattamente due Elfi fanno un piccolo errore. Quanti Troll sono seduti a quel tavolo?
Fantasy belga
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Ci sono 20 trolls.
Allora... negli schemi chiamo (ho una fantasia...) E gli elfi, T i trolls, e M gli elfi mentitori...
Cominciamo col vedere che se ci fosse una sequenza TT, allora il troll, per poter mentire, dovrebbe avere vicino un altro troll, quindi TTT, e così via, senza poter mai inserire elfi. Quindi non ci sono sequenze TT. Consideriamo ora gli elfi. Ogni elfo (tranne i due mentitori) ha vicino un troll e un altro elfo, quindi
EET: vicino a quest'ultimo troll c'è ovviamente un altro elfo per il motivo di cui sopra, quindi la sequenza diventa EETE; a questo punto abbiamo un elfo, quindi diventa EETEE e così via...
Ora passiamo ai mentitori. I mentitori possono avere due vicini T o due vicini E. Entrambi i casi sono possibili, e le configurazioni risultano:
...EETMTEE... oppure ...ETEMETE...
Ok. Fine delle premesse. Tentiamo ora di costruire una configurazione funzionante. Parto da uno dei due mentitori e scelgo una a caso delle due configurazioni, ad esempio EME.
Da entrambe le parti, per quanto sopra, si va avanti con TEETEETEE... da qualche parte dovrà interrompersi per far posto all'altro mentitore.
Supponiamo di interrompere la catena dopo una T, e di posizionare il gruppo EME. Questo ci porta ad avere usato:
3 creature per il gruppo EME;
3k creature per i gruppi TEE + 1 per il troll sparso
3 creature per il gruppo EME;
ne avanzano un numero $ \equiv 2 \mod 3 $. Andando avanti si finirà per finire con una E, che confinerebbe con la E iniziale del gruppo EME, assurdo
Dopo una T inoltre non posso posizionare il gruppo TMT per il solito motivo (due troll vicini)
Supponiamo invece di interrompere dopo una E; non posso mettere EME per ovvi motivi, quindi devo mettere per forza TMT: così funziona, poichè uso:
1) 3 creature per E-M-E
2) 3a creature in gruppi TEE
3) 3 creature nel gruppo TMT
4) 3b creature negli altri gruppi TEE con cui chiudo il cerchio.
Ora, contando, vedo che ho posizionato:
1) 0 trolls
2) a trolls
3) 2 trolls
4) b trolls
Poichè 3a+3b=54, a+b=18, e perciò il numero dei trolls è 18+2=20.
Sperando sia tutto vero,
ciao!!!
Allora... negli schemi chiamo (ho una fantasia...) E gli elfi, T i trolls, e M gli elfi mentitori...
Cominciamo col vedere che se ci fosse una sequenza TT, allora il troll, per poter mentire, dovrebbe avere vicino un altro troll, quindi TTT, e così via, senza poter mai inserire elfi. Quindi non ci sono sequenze TT. Consideriamo ora gli elfi. Ogni elfo (tranne i due mentitori) ha vicino un troll e un altro elfo, quindi
EET: vicino a quest'ultimo troll c'è ovviamente un altro elfo per il motivo di cui sopra, quindi la sequenza diventa EETE; a questo punto abbiamo un elfo, quindi diventa EETEE e così via...
Ora passiamo ai mentitori. I mentitori possono avere due vicini T o due vicini E. Entrambi i casi sono possibili, e le configurazioni risultano:
...EETMTEE... oppure ...ETEMETE...
Ok. Fine delle premesse. Tentiamo ora di costruire una configurazione funzionante. Parto da uno dei due mentitori e scelgo una a caso delle due configurazioni, ad esempio EME.
Da entrambe le parti, per quanto sopra, si va avanti con TEETEETEE... da qualche parte dovrà interrompersi per far posto all'altro mentitore.
Supponiamo di interrompere la catena dopo una T, e di posizionare il gruppo EME. Questo ci porta ad avere usato:
3 creature per il gruppo EME;
3k creature per i gruppi TEE + 1 per il troll sparso
3 creature per il gruppo EME;
ne avanzano un numero $ \equiv 2 \mod 3 $. Andando avanti si finirà per finire con una E, che confinerebbe con la E iniziale del gruppo EME, assurdo
Dopo una T inoltre non posso posizionare il gruppo TMT per il solito motivo (due troll vicini)
Supponiamo invece di interrompere dopo una E; non posso mettere EME per ovvi motivi, quindi devo mettere per forza TMT: così funziona, poichè uso:
1) 3 creature per E-M-E
2) 3a creature in gruppi TEE
3) 3 creature nel gruppo TMT
4) 3b creature negli altri gruppi TEE con cui chiudo il cerchio.
Ora, contando, vedo che ho posizionato:
1) 0 trolls
2) a trolls
3) 2 trolls
4) b trolls
Poichè 3a+3b=54, a+b=18, e perciò il numero dei trolls è 18+2=20.
Sperando sia tutto vero,
ciao!!!
Ultima modifica di darkcrystal il 20 apr 2006, 22:38, modificato 3 volte in totale.
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Ah, mi sono dimenticato. Siccome le configurazioni dei mentitori vanno usate entrambe, non importa che io sia partito da una piuttosto che dall'altra: basta invertire tutto e dovrebbe funzionare.
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Sapendo che i troll (T) mentono sempre e che gli elfi (E) dicono sempre la verità e che tutti affermano di avere a fianco un troll e un elfo le maniere possibili per disporli attorno ad un tavolo sono solo due:
1) ...TTTTTTTTT...
2) ...TEETEETEE...
La disposizione 1) è corretta ma il testo del problema ci dice che ci sono almeno due elfi quindi è da scartare
Analizziamo la disposizione 2)
Con tale disposizione si riesce a riempire tutti i 60 posti correttamente (essendo composta da moduli di 3 TEE)
Dobbiamo però considerare che ci sono due elfi che sbagliano (e), quindi mentono.
Quindi o hanno a fianco 2 elfi (EeE) o hanno a fianco 2 troll (TeT).
La disposizione EeE ovviamente deve essere inserita nella disposizione complessiva e perciò sarà così ...TEeE... e prima e dopo i soliti moduli TEE.
Ma siccome il modulo TEeE è lungo 4 non possiamo sistemare due elfi mentitori di questo tipo perchè il totale deve essere 60 e 60 non è della forma $ 8+3k $.
La disposizione TeT ovviamente deve essere inserita nella disposizione complessiva e perciò sarà così ...TeTEE... e prima e dopo i soliti moduli TEE.
Ma siccome il modulo TeTEE è lungo 5 non possiamo sistemare due elfi mentitori di questo tipo perchè il totale deve essere 60 e 60 non è della forma $ 10+3k $.
L'unica possibilità rimane sistemare un elfo mentitore TeT e un elfo mentitore EeE.
In questo caso si avrà ...TEeE...TeTEE... e prima, dopo e in mezzo i soliti moduli TEE.
Si nota che tale disposizione è corretta perchè 60 è della forma $ 9+3k $. Infatti $ 60 = 9+3\cdot 17 $.
Quindi abbiamo 17 moduli TEE più i due moduli TeTEE e TEeE.
I troll quindi saranno $ 17\cdot 1+2+1=20 $
Gli elfi saranno $ 60-20=40=17 \cdot 2+3+3 $
Si noti che i due moduli "anomali" possono essere inseriti in qualsiasi ordine e in qualsiasi punto della disposizione, sempre tra due moduli TEE o anche vicini tra di loro, e che è indifferente in che modo comincia la disposizione essendo il tavolo circolare.
P.S. In quanto grande appassionato di fantasy non potevo lasciarmi sfuggire questo problema!
P.S.2 Scusate mi sono accorto dopo che la soluzione era gia stata postata!
1) ...TTTTTTTTT...
2) ...TEETEETEE...
La disposizione 1) è corretta ma il testo del problema ci dice che ci sono almeno due elfi quindi è da scartare
Analizziamo la disposizione 2)
Con tale disposizione si riesce a riempire tutti i 60 posti correttamente (essendo composta da moduli di 3 TEE)
Dobbiamo però considerare che ci sono due elfi che sbagliano (e), quindi mentono.
Quindi o hanno a fianco 2 elfi (EeE) o hanno a fianco 2 troll (TeT).
La disposizione EeE ovviamente deve essere inserita nella disposizione complessiva e perciò sarà così ...TEeE... e prima e dopo i soliti moduli TEE.
Ma siccome il modulo TEeE è lungo 4 non possiamo sistemare due elfi mentitori di questo tipo perchè il totale deve essere 60 e 60 non è della forma $ 8+3k $.
La disposizione TeT ovviamente deve essere inserita nella disposizione complessiva e perciò sarà così ...TeTEE... e prima e dopo i soliti moduli TEE.
Ma siccome il modulo TeTEE è lungo 5 non possiamo sistemare due elfi mentitori di questo tipo perchè il totale deve essere 60 e 60 non è della forma $ 10+3k $.
L'unica possibilità rimane sistemare un elfo mentitore TeT e un elfo mentitore EeE.
In questo caso si avrà ...TEeE...TeTEE... e prima, dopo e in mezzo i soliti moduli TEE.
Si nota che tale disposizione è corretta perchè 60 è della forma $ 9+3k $. Infatti $ 60 = 9+3\cdot 17 $.
Quindi abbiamo 17 moduli TEE più i due moduli TeTEE e TEeE.
I troll quindi saranno $ 17\cdot 1+2+1=20 $
Gli elfi saranno $ 60-20=40=17 \cdot 2+3+3 $
Si noti che i due moduli "anomali" possono essere inseriti in qualsiasi ordine e in qualsiasi punto della disposizione, sempre tra due moduli TEE o anche vicini tra di loro, e che è indifferente in che modo comincia la disposizione essendo il tavolo circolare.
P.S. In quanto grande appassionato di fantasy non potevo lasciarmi sfuggire questo problema!
P.S.2 Scusate mi sono accorto dopo che la soluzione era gia stata postata!
