Newsgroup: it.hobby.enigmi
Titolo: Prova d'amicizia

Supponiamo che comunque si scelgano 30 persone da un gruppo di 61
esista sempre tra le 31 rimanenti una persona amica con tutte e 30.
Si puo' affermare allora che esista una persona amica con tutte e 60 le
altre persone del gruppo e perchè?


spoiler
|
|
|
|
|
|
|
|
|
|
|
|
|
No, non si può affermare. Supponiamo che sia:
1 non amico di 2
2 non amico di 3
3 non amico di 4
.
.
60 non amico di 61
61 non amico di 1
Allora il gruppo qualunque di 30 ha, al massimo, nel gruppo restante di
31, 30 non-amici e quindi almeno uno è amico di tutti e trenta.
Ciao!!!  :o)
Livio

 31, 30 non-amici e quindi almeno uno è amico di tutti e trenta.
Se come gruppo di 30 scegliessi, per esempio, tutti i numeri pari (2,
4, 6 .. 60),
allora ciascuno dei 31 dispari rimanenti sarebbe amico di soli 28 del
primo gruppo (non lo sarebbe di quelli "adiacenti"). Con l'eccezione di
1 e 61 che sarebbero amici di soli 29 del gruppo (di tutti tranne,
rispettivamente, di 2 e di 60).
No?

 Ma l'amicizia è reciproca?
Allora sono fregato!  :o)
Il mio ragionamento dovrebbe stare in piedi soltanto con sentimenti
asimmetrici del tipo A sta simpatico a B, che probabilmente non era
nelle intenzioni del proponente. Sorry.
Ciao!!!  :o)
Livio

 le altre persone del gruppo e perchč?
Sě
Guardiamo alla relazione opposta, quella di non amicizia. Una persona "amica 
di tutti" (da ora in avanti un "simpaticone") č un punto isolato rispetto a 
questa relazione. Se vogliamo che in ogni gruppo di 31 persone ci sia almeno 
un punto isolato (un semplice "simpatico"), allora DEVE esistere un 
simpaticone.
Se disegnamo il grafo della relazione di non amicizia, vediamo che č una 
foresta di componenti connesse, ovvero un insieme di gruppi nei quali ognuno 
č non amico di qualcun altro. Possono essere semplici gruppi di due persone, 
ovvero due persone ognuna delle quali č amica di tutti tranne dell'altra 
("il cane e il gatto"), o gruppi piů numerosi. Al limite potrebbe essere un 
solo unico grafo.
Se nel gruppo di 61 fossero tutti "simpaticoni" o coppie di "cani e gatti", 
allora sarebbe impossibile formare gruppi da 31 senza un simpaticone o un 
cane separato dal suo gatto (e senza il gatto, il cane č simpatico a tutti).
Ma se non ci fosse nessun simpaticone, allora dovrebbe esserci almeno un 
gruppetto di 3 o piů persone a ognuna delle quali non va giů qualcun altro 
del gruppetto ("i colleghi").
La presenza dei "colleghi" permette di formare sempre almeno un gruppo di 31 
persone che non lasci nessun cane senza gatto o nessun collega isolato.
Fuor di metafora: se non c'č una persona amica di tutti, č sempre possibile 
trovarne 31 (ma qualsiasi numero dispari, direi) nessuna dell quali sia 
amica delle altre 30.
Quindi, se č vero che in ogni gruppo di 31 c'č un simpatico, deve esistere 
un simpaticone.
-- 
Ciao, Silv:o)



Mi accorgo adesso di aver male interpretato.
Io , nella frase "Supponiamo che comunque si scelgano 30 persone da un 
gruppo di 61 esista sempre tra le 31 rimanenti una persona amica con 
tutte e 30" intendevo "con tutte le altre 30 dei 31 rimanenti" non 
"con tuttte le 30 persone scelte".
Infatti non capivo perché non avesse semplicemente scritto: 
"Supponiamo che comunque si scelgano 31 persone da un gruppo di 61 
esista sempre una persona amica con le altre 30".
Anche questo può essere trattato con lo stratagemma di invertire la 
relazione. Uso "nemico" al posto di "non amico" per semplicità, anche 
se in italiano non è esettamente così.
Prendiamo a caso una persona a cui diamo un cappello rosso, poi 
chiediamo a tutte le persone che non sono sue amiche di indossare un 
cappello rosso. Poi chiediamo a chiunque non sia amico di tutti i 
rossi (ovvero a chiunque sia nemico di almeno un rosso), di unirsi a 
loro. Terminati i rossi, si sceglie un altro colore, lo si consegna a 
uno a caso e si chiede ai suoi nemici e poi ai nemici dei suoi nemici 
di indossare lo stesso colore di cappello. Alla fine tutti avranno un 
cappello, e gli amici di tutti avranno ognuno un proprio colore 
esclusivo.
Traduciamo l'enuciato:
Supponiamo che comunque si scelgano 30 palline da un urna di 61
esista sempre tra le 31 rimanenti una pallina di colore diverso da 
tutte e 30.
Si puo' affermare allora che esista una pallina di colore diverso da 
tutte e 60 le
altre palline dell'urna e perchè?
La risposta è ovviamente sì.
Se non esistesse, allora tutti i colori avrebbero due o più palline.
Prendendo la metà delle palline di ciascun colore (per i colori che 
hanno un numero dispari di palline, una volta prendiamo la metà per 
eccesso e una per difetto), avrei diviso le 61 palline in due gruppi 
da 31 e 30. Si vede facilmente che nel gruppo da 31 non c'è nessuna 
pallina di colore differente da tutte quelle del gruppo di 30.
Per completezza traspongo anche il problema per come lo avevo 
interpretato io:
Supponiamo che comunque si scelgano 31 palline da un urna di 61
esista sempre una pallina di colore diverso dalle altre.
Si puo' affermare allora che esista una pallina di colore diverso da 
tutte e 60 le
altre palline dell'urna e perchè?
La risposta è sì.
Se non esistesse, allora dovrebbe esistere almeno un colore con più di 
2 palline.
Questo basta a garantire la possibilità di scegliere un gruppo di 31 
palline senza dover utilizzare una pallina singola, cosa impossibile 
solo nel caso in cui tutti i colori avessere al massimo 2 palline.
--
Ciao, Silv:o)