Il Silenzio

[franco]

Un altro problema da www.diophante.fr (E5928).
Non è difficile ma mi ha "sbloccato un ricordo" (*)

Cinque studenti di ingegneria fanno amicizia con altrettante studentesse di lingue che propongono loro una serata al cineforum in facoltà di Magistero; segue dibattito.
I ragazzi, nella malcelata speranza di un ulteriore piacevole seguito dopo il dibattito, accettano volentieri e si presentano puntuali in aula magna.

Purtroppo il film della serata è "Il Silenzio", regia di Ingmar Bergman, 95 minuti in bianco e nero, lingua originale e sottotitoli ...
Nonostante la loro buona volontà, tutti e cinque si assopiscono per due volte durante la proiezione.
Considerati due a due, c'è sempre stato un momento in cui entrambi i ragazzi erano contemporaneamente addormentati.
Dimostrare che c'è stato un momento in cui a dormire erano almeno in tre ragazzi.
... naturalmente, al dibattito ha fatto seguito solo un mesto ritorno a casa dei cinque giovanotti!

ciao

Franco


(*) Il ricordo è attorno al 1979; io ero uno degli studenti di ingegneria.
Escluso il fatto che eravamo in tre e non in cinque, è tutto vero!

P.S. il testo originale del problema è un po' diverso ma mi sono divertito ad adattarlo ai miei ricordi di gioventù.
Cinq amis de Diophante se sont donné rendez-vous pour écouter la brillante conférence de Laurent Lafforgue sur les catégoriques syntaxiques pour les motivations de Nori. Comme l’exposé a été très ardu, chacun d’eux s’est assoupi deux fois et pour chaque paire d’amis, il y a toujours eu un moment où l’un et l’autre se sont assoupis. Prouver qu’à un certain moment, trois d’entre eux se sont simultanément assoupis.

[Gianfranco]

Grazie per il ricordo, Franco!
---
Provo a risolverlo...
---
1) Ciascun ragazzo può essere in uno di due stati:
sveglio = 1
addormentato = 0
---
2) Supponiamo per assurdo che non ci siano state almeno-terne di ragazzi addormentati.
Teniamo inoltre conto che tutte le coppie possibili si sono addormentate almeno una volta.
Allora le possibilità sono:
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
---
Attenzione: non leggere il seguito perché deriva da una mia interpretazione errata del testo.
---
3) In questa ipotesi risulta che ogni ragazzo deve essersi addormentato per 4 volte. Interpretazione errata: 2 o più volte consecutive possono essere unite e formare un unico pisolino.
---
4) Ma il testo dice che ciascuno si è addormentato 2 volte. Vedi riga precedente.
---
5) Quindi ci sono state almeno-terne di ragazzi addormentati.
---
Salvo errori, omissioni & fraintendimenti

---
P.S. Però ho dei dubbi sulla mia soluzione: l'ipotesi che ciascuno si è addormentato 2 volte mi sembra debole. Infatti la soluzione funzionerebbe anche se ciascuno si fosse addormentato 3 volte. Buona notte!

[franco]

Sto facendo qualche prova anche io ... con convenzioni grafiche opposte (in orizzontale e 1=addormentato)

silenzio.png (4.86 KiB) Visto 69699 volte

Per come la interpreto io, i sonnellini sono i tratti in giallo: due o più slot consecutivi sono parte dello stesso sonnellino.

Deto ciò, non trovo modo di combinare le colonne attribuendo solo due sonnellini ad ogni ragazzo.
Ma soprattutto, il fatto che non riesca a trovare il modo non equivale a dimostrare che ciò sia impossibile.

[Gianfranco]

Deto ciò, non trovo modo di combinare le colonne attribuendo solo due sonnellini ad ogni ragazzo.
Ma soprattutto, il fatto che non riesca a trovare il modo non equivale a dimostrare che ciò sia impossibile.

Intendevi una cosa come quella qui sotto?
Ho usato la tua convenzione.

silenzio.png (14.11 KiB) Visto 69563 volte

Le possibili coppie di 5 elementi sono 10.
Se per una volta dormono in 3 allora corrispondono a 3 coppie.
Perciò bastano 8 colonne per rappresentare la situazione.
Se ho capito bene la condizione: "una volta a dormire erano in 3".

[franco]

Secondo me, il quesito richiede di dimostrare l'impossibilità di trovare una combinazione che rispetti queste tre condizioni:
- tutte le possibili 10 coppie hanno un momento in cui entrambi dormono
- tutti i ragazzi dormomo per 2 periodi (più o meno lunghi)
- non ci sono momenti in cui 3 ragazzi che dormono in contemporanea

Trovare combinazioni che ne rispettino solo due è facile (la mia vedeva un ragazzo che dorme per 3 periodi intervallati da momenti di veglia; la tua ultima ha un momento in cui a dormire sono in 3) ... la complessità è dimostrare che una combinazione del genere non può esistere.

[Gianfranco]

Trovare combinazioni che ne rispettino solo due è facile... la complessità è dimostrare che una combinazione del genere non può esistere.

Concordo.
Anch'io sto esplorando soluzioni incomplete, nei miei limiti.
Forse questi tentativi falliti posso portare a intuire il motivo dell'impossibilità.
A proposito di soluzioni che rispettano solo 2 condizioni, propongo questa in cui solo una persona dorme 3 volte:

SILENZIO2.png (12.96 KiB) Visto 69205 volte

All'inizio, A individua due intervalli disgiunti di "sonno".
Poi, B, C, D aggiungono ciascuno un intervallo disgiunto dagli altri.
In tutto fanno 5 intervalli.
Alla fine, per E rimangono 4 posti su 4 intervalli disgiunti e forse sta qui l'impossibilità di sistemarli in modo da formare solo 2 intervalli.
Ma, appunto bisognerebbe dimostrare che è sempre impossibile.