Newsgroup: it.hobby.enigmi
Titolo: Il corso di specializzazione

 Un gruppo di ricercatori comincia a frequentare un corso.
 Molti vengono da Paesi diversi perciò risulta che:
 -ognuno di loro conosce reciprocamente al massimo 4 ricercatori del corso.
 -se due persone del corso non si conoscono hanno però un conoscente
 reciproco in comune che frequenta il corso.
 In base a questi dati qual è il massimo numero
 di persone che sta per frequentare quel corso?

anbra1 wrote:
 >  Un gruppo di ricercatori comincia a frequentare un corso.
 >  Molti vengono da Paesi diversi perciň risulta che:
 >  -ognuno di loro conosce reciprocamente al massimo 4 ricercatori del 
    >   corso.
 >  -se due persone del corso non si conoscono hanno perň un conoscente
 >  reciproco in comune che frequenta il corso.
 >  In base a questi dati qual č il massimo numero
 >  di persone che sta per frequentare quel corso?
 >
 >
Sperando di aver capito bene, interpreto la seconda affermazione come:
-se due persone del corso non si conoscono hanno perň ALMENO un 
conoscente reciproco in comune che frequenta il corso.
Spoiler
.
.
.
.
.
.
Non piu' di 17.
Un frequentatote conosce al massimo 4  persone e ciascuna di queste non 
piu' di altre 3
Si tratta di disegnare un grafo dove da ogni nodo dipartono 4 archi  al 
massimo e che si possa passare da ogni nodo a qualunque altro 
percorrendo non piu' di 2 archi.
Per il momento ci riesco  in 14.
          01-----02
           |     |
           |     |
    03----04     05----06
     |                 |
     |      13 14      |
     |                 |
    07----08     09----10
           |     |
           |     |
          11-----12
Gli archi da aggiungere sono:
01-11, 01-10, 02-07, 02-12
03-06, 03-12, 04-13, 04-14
05-13, 05-14, 06-11, 07-10
08-13, 08-14, 09-13, 09-14
Ecco ad esempio lo specchietto delle conoscenze della persona num.1
01- -- -02
01- 04 -03
01- -- -04
01- 02 -05
01- 10 -06
01- 02 -07
01- 11 -08
01- 10 -09
01- -- -10
01- -- -11
01- 11 -12
01- 04 -13
01- 04 -14
Come si vede ci sono molte sovrapposizioni; ad es 13 e 14 hanno 4 
conoscenti in comune. Questo fa sperare in un miglioramento.
Ciao


Sicuramente non ho capito bene il problema, ma mi viene da dire che
possono essere infiniti, se "per un puro caso" il conoscente in comune
e' lo stesso.
1 conosce 2-3-4-5
2 conosce 6-7-8-1
6 conosce 9-10-1-2
9 conosce 11-12-6-1
ecc.

 ecc.
E sei sicuro che dati ogni volta due ricercatori del tuo insieme esista
un ricercatore conoscente di entrambi?

 Non piu' di 17.
Giusto !!!
Resta da vedere però se esiste un grafo con 17 nodi e questo è un
esercizio
per sw potenti dato che risulta un po' difficile la ricerca manuale.
Poichè non era specificato puoi valutare anche l'ipotesi
"-se due persone del corso non si conoscono hanno però un SOLO
conoscente reciproco in comune che frequenta il corso."
Ciao!

 un ricercatore conoscente di entrambi?
Me ne sono accorto ora ... per 1 potrebbe valere il motto "conosci te
stesso"? :-))))

 conoscente reciproco in comune che frequenta il corso."
Basandosi su un grafo di Petersen, (che risolve il tuo problema per 10 
persone con 3 conoscenze reciproche),
è facile ottenere una soluzione per 15 frequentatori.
http://en.wikipedia.org/wiki/Petersen_graph
ciao

 stesso"? :-))))
Ma non sarebbe massimo pur ammettendo l'ipotesi non ovvia che ognuno conosca
se stesso
come invitava a fare l'oracolo di Delfi prima e in sintesi Socrate poi

 un ricercatore conoscente di entrambi?
Mi è sfuggita la tua ipotesi che esista un conoscente comune a tutti
ma così questo non ne avrebbe massimo 4

 per sw potenti dato che risulta un po' difficile la ricerca manuale.
Ci provo con un caso limite (a stella) ma, se non mi e' sfuggito 
qualcosa (ipotesi piu' che probabile, visto che non mi pare troppo 
difficile), valido secondo le ipotesi.
A conosce B, C, D ed E.
Ognuno tra B, C, D ed E conosce A e altre 3 persone, queste ultime 
distinte per ognuno di loro.
3 x 4 = 12 + 5 = 17
bye
-- 
Paolo Lucchesi
email: plucchesiNOSPAM(at)NOSPAMtin(dot)NOSPAMit
homepage: 
http://www.paololucchesi.it
"Non viviamo in un mondo perfetto (per fortuna)"

 3 x 4 = 12 + 5 = 17
Ma poi devi realizzare i legami degli altri 12 nodi tra loro
in modo che da ogni nodo partano fino a 4 archi
e che tra due nodi ci sia sempre o un legame diretto
o mediato da un nodo tra due archi.
Prova a realizzare un grafo con 17 nodi in cui
tra due nodi non direttamente collegati esista un solo nodo intermedio

Salve a tutti, sono nuovo del NG.
La soluzione a 17 nodi dovrebbe essere impossibile (dimostrazione
lunghina ma facile)
Inoltre, banalmente, se esiste una persona che conosce in tutto altre
n persone (1 <= n <= 4), allora detto M il numero massimo di persone
che frequentano il corso: M <= 1 + 4n
ciao

 che frequentano il corso: M <= 1 + 4n
Questo invece è vero.