E’ quì la festa ?

Mi sono imbattuto in un bel gioco di logica che vi propongo:

Calcolare il minimo numero n di invitati ad una festa necessario affinchè almeno tre di loro si conoscano oppure almeno tre di loro non si conoscano.

una precisazione  se A conosce B anche B conosce A

Pubblicato su gioco. 26 Comments »

26 Risposte to “E’ quì la festa ?”

  1. profepa Says:

    Mmmmm… sembra troppo facile…Penso proprio che aspetterò qualche spunto!

  2. Francesco (profefra) Says:

    Escludo subito che gli invitati siano 3 !!!!!
    Vi ho dato un grande aiuto…..non vi resta che provare per n > 3.

  3. profepa Says:

    Provo con 5!!!

  4. lalla91 Says:

    proviamo
    allora
    A conosce B
    B conosce C
    C conosce A
    e questi sono i 3 che si conoscono..poi
    A conosce D che però non conosce B e C
    B conosce E
    quindi le persone che non si conoscono sono E, D e C
    il numero minimo dovrebbe essere 5

  5. Francesco (profefra) Says:

    5 non va bene, infatti se le relazioni sono le seguenti:

    A —> B
    A—->C
    B—–>D
    C—–>E
    D—–>E
    la proposizione è falsa.
    Per evidenziare meglio la cosa disegnate il pentagono ABCDE in cui i lati rappresentano le relazioni.

  6. profe3 Says:

    Io direi 4: 3 si conoscono tra di loro uno solo dei tre conosce ilquarto che però non conosce gli altri due così 3 si conocono a vicenda e 3 no.
    E poi…non c’è due senza tre e…il quarto vien da sé!

  7. profema Says:

    4 non va bene, perché se la relazione è così stabilita la proposizione è falsa:

    a R c
    b R c

    (Dimmi se ho capito almeno la domanda…)

  8. Francesco (profefra) Says:

    Forse volevi scrivere:

    a R c
    b R d

    infatti se questi sono i rapporti tra gli invitati la proposizione è falsa.
    Invece l’istanza a R c e b R c rende la proposizione vera in quanto ci sarebbero a,b e d che non si conoscono.
    Preciso che la relazione di conoscenza non è transitiva, ma solo simmetrica.

  9. profema Says:

    Sì, ho sbagliato a trascrivere. L’unica cosa che ho chiara è che la relazione di conoscenza non è transitiva…

    Dunque… comunque si definisca una relazione deve sempre esistere una terna che si conosce (triangoli) o una terna che non si conosce (tre punti isolati) Ho capito bene?

  10. Francesco (profefra) Says:

    Le persone che non si conoscono possono anche non essere punti isolati, vale a dire che possono conoscere altre persone, ma non conoscersi tra di loro.
    Forse scomponendo il problema così è più chiaro:

    P1 = esistono 3 che si conoscono tra di loro
    P2 = esistono 3 persone che non si conoscono
    P = P1 V P2
    Occorre trovare il numero minimo di persone che rende P sempre vera (per ogni combinazione di rapporti di amicizia).
    Per stabilire che 4 persone non erano sufficienti è bastato trovare il controesempio seguente:
    a R b e c R d.

  11. Francesco (profefra) Says:

    Specifico meglio la scomposizione del problema:

    P1 = esistono almeno 3 persone che si conoscono tra di loro
    P2 = esistono almeno 3 persone che non si conoscono
    P = P1 V P2

  12. profema Says:

    Al massimo due si conoscono e al massimo due si conoscono. nonp1 e nonp2

  13. profema Says:

    (Scrivo queste cose mentre mi preparo per uscire… forse sparo stupidaggini peggio dei miei studenti… i miei studenti che ne dicono, visto che si sono rivelati dei bravi risolutori?)

  14. profe3 Says:

    ma il numero dei componenti non doveva essere maggiore di 3!

  15. Francesco (profefra) Says:

    Ricapitoliamo:

    “Calcolare il minimo numero n di invitati ad una festa necessario affinchè almeno tre di loro si conoscano oppure almeno tre di loro non si conoscano.”

    P1 = esistono almeno 3 persone che si conoscono tra di loro
    P2 = esistono almeno 3 persone che non si conoscono tra di loro

    P = P1 V P2

    se n è la soluzione allora qualunque associazione tra le persone deve rendere P vera.

    Escludiamo 2 e vediamo perchè.

    Per n = 2 gli invitati sono A e B.
    Quali potrebbero essere i rapporti tra A e B ?

    A ——– B (uso la linea tratteggiata per indicare che A e B si conoscono)
    si vede subito che sia P1 che P2 sono false quindi è falsa P.
    Mi sono imbattuto subito in un caso che rente P falsa quindi 2 non va bene (con 2 P è sempre falsa).

    Vediamo adesso con n = 3

    A——-B A———-C B——–C
    Questa associazione rende P1 vera e quindi P, ma devo essere certo che P sia vera per ogni possibile associazione.

    Quindi esaminiamo un’altra possibile configurazione…

    A B C (se tra 2 lettere non c’e’ linea significa che i due non si conoscono )
    Questa combinazione rende P2 vera e quindi anche P.

    Ma se la configurazione è una delle seguenti?

    A ——— B B ——- C

    oppure

    A ——– B C ecc.

    P1 e P2 sono false e quindi P è falsa.

    Questo mi assicura che 3 non va bene.

    4, potrebbe andare ?

    No !

    presento subito il caso sfavorevole

    A —– B C —— D (ce ne sono altri di casi sfavorevoli, ma ne basta 1 ).

    5, potrebbe andare ?

    ……………………………………………Dormiamoci sopra………lasciamo lavorare il subconsio……magari ci svegliamo con la soluzione.

    Buona notte !!!!

  16. profema Says:

    Che deficiente! ho fatto un rigiro per dimostrare che era vera la negazione di p!
    Ma Francesco… hai già detto che 5 non andava bene…

  17. Francesco (profefra) Says:

    Si, lo confermo.

  18. profepa Says:

    Alla faccia di chi ha detto che era facile….. 🙂

  19. profe3 Says:

    Io forse ancora non ho capito… noi vogliamo dimostrare che P1vP2 è una tautologia giusto? quindi che a prescindere dai valori di verità di P1 e P2 P1vP2 è vera ma poichè la tavola dell’v è sempre vera salvo nel caso in cui P1 e P2 siano entrambe false per non essere vera occorrerebe che non vi fossero ne tre persone che non si conoscono nè 3 che si conoscono… oddio mi sono persa,,, sono peggio dei ragazzi!

  20. profe3 Says:

    perchè quando sono sul più bello è sempre l’ora di andare a prendere i figli!!!!
    a domani

  21. profema Says:

    Secondo me, se vogliamo rientrare a scuola… dobbiamo cancellare questo post con tutti i commenti… anzi basta cancellare i commenti…

  22. _Niccolò_ Says:

    Il numero minimo forse è 6

    3 sono collegati tra loro e 3 no e comunque si scambiano rimangono sempre tre collegati e tre no

  23. Francesco (profefra) Says:

    Esatto, il numero minimo è 6.

  24. profepa Says:

    E bravo Niccolò!
    Profefra, il nostro risolutore ha detto a scuola che è stato ispirato dal tuo riferimento al pentagono e così ha pensato all’esagono…Attento ed efficace!

  25. Francesco (profefra) Says:

    Sono contento che Niccolò abbia risolto il quesito, ma lo sono ancora di più sapendo di essergli stato d’aiuto.


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: