Newsgroup: it.economia.borsa
Titolo: Uno strano torneo

Ad un torneo di calcio partecipano 16 squadre.
Al termine, risulta che, scelte comunque 3 squadre,
almeno due si sono incontrate tra di loro.
Determinare il numero minimo di incontri disputati.
E, in generale, se si deve verificare questa condizione,
qual č il numero minimo di incontri per n squadre?

 incontri per n squadre?
bastano due gironi all'italiana da 8 squadre e sceltene tre, due hanno 
per forza giocato nello steso girone.

 per forza giocato nello steso girone.
E' la risposta esatta.
Semplice, ma assolutamente fuori portata dalla maggior parte dei
matematici.
Che si mettono a fare i calcoli e per lo piů arrivano alla risposta:
92 partite (invece di 56); e in generale      (n-2)(n-3)/2+1,
risultato che si ottiene facendo giocare a n-2 squadre tutte le
partite fra loro, mentre le due squadre rimanenti giocano una
partita fra loro.
A questo punto, se vuoi, puoi completare con la formula che
generalizza la soluzione del numero minore di incontri quando le
squadre partecipanti sono n.

 partecipanti sono n.
meglio di no, non sono un matematico. Nelle formule mi ci perderei :-)

 meglio di no, non sono un matematico.
Adesso ho capito perchč ci sei arrivato subito...

Adesso ho capito perchè ci sei arrivato subito...
Guarda che un matematico non ti darebbe la risposta senza sapertela
dimostrare, e che questa risposta dia veramente il numero minimo è tutto
da vedere, almeno per quanto mi riguarda :)

 Adesso ho capito perchè ci sei arrivato subito...
Esatto !



no invece. Un girone solo prevede molte piu' partite di due gironi.
Ogni squadra deve giocare contro tute le altre, ossia 15 partite. Quindi 
sono 15*16/2 = 120 partite
Con due gironi ogni squadra gioca 7 partite: 7*8/2 = 28 per 2 gironi = 56 
partite + 1 per la finale tra le due migliori ==> 57.
Piu' di due gironi, e non hai la garanzia che con tre squadre scelte a 
caso due si siano scontrate, puoi pescarle in tre gironi iniziali diversi 
e tutte e tre eliminate.
Se pensi all'eliminazione diretta e' ancora peggio, 8 squadre non passano 
il primo turno, se peschi a caso non hai garanzia di non prenderne 3 
eliminate subito.

 dimostrare, e che questa risposta dia veramente il numero minimo
Questa E' la soluzione (numero minimo di incontri).
Anche se in teoria il minimo dovrebbe essere
(intero_arrot_per_eccesso (C(n,3)/(n-2))    nel caso particolare 40 incontri
teorici anzichè i 56 effettivi pratici)
Ovviamente, non lo so (nè mi sognerei mai)  dimostrare.
Non mi piacciono le seghe mentali...
:-)
Soluzione:
per n squadre pari             n(n-2)/4       partite
per n     "       dispari          (n-1)^2/4     partite
Nota: Lo sa perfettamente che questo è il minimo chi si diletta nelle 
riduzioni
totocalcio a garanzia n-1 con la correzione di 0-3 errori. 

 eliminate subito.
Tutto vero.
Per me è più che sufficiente come dimostrazione... :-) 


Questa è anche facile da dimostrare.
Supponiamo di raggruppare le squadre in gruppi tali che le squadre 
all'interno di ciascun gruppo hanno tutte giocato fra di loro.
Se ottenessi più di tre gruppi contraddirei certamente le ipotesi.
Ho quindi non più di due gruppi di squadre che hanno tutte giocato fra di 
loro.
A questo punto la soluzione più "economica" sono appunto (abbastanza 
ovviamente) i due gironi all'italiana con ciascuno la metà delle squadre.
-- 
Era un popolo strano e sfortunato:
il benessere li aveva privati di tutto.
(Stefano Benni - La compagnia dei Celestini)

loro.
Sě, questo č vero se partizioni l'insieme di squadre in gruppi che hanno
giocato tutte fra di loro.  Ma a me non pare ovvio che sia l'unico tipo
di partizionamento da considerare.
Insomma, a intuito direi anch'io che č la soluzione giusta, ma rimane il
fatto che una risposta data a intuito e una dimostrata son due cose
diverse :)

 diverse :)
ma io te l'ho dimostrata: con piu' di due gironi, o con l'eliminazione 
diretta, non hai la certezza che 3 squadre prese a caso almeno 2 si siano 
incontrate.
Quindi o 1 girone o 2, e con 1 girone si giocano piu' partite che con 2
Non ti sembra una dimostrazione matematica perche' non servono integrali 
ed equazioni differenziali da risolvere, ma e' una dimostrazione logica a 
tutti gli effetti.

incontrate.
Sě, fin qui ci siamo.  Ma ammetti che ci sia un solo girone, e che non
sia un girone all'italiana, cioč non tutti incontrino ogni altro.
Sicuro che in questo caso non si possa fare di meglio?  A intuito dico
anch'io che non si puň, ma non vedo la dimostrazione.

 anch'io che non si può, ma non vedo la dimostrazione.
Allora: sai determinare la riduzione massima teorica?
Cioè il numero minimo teorico di partite (senza ridondanza) che
garantiscono la richiesta? (Scelte comunque 3 squadre, almeno 2
si sono incontrate tra di loro)
Seguimi.
Il numero totale di terzine (cioè gruppi di 3 squadre) è Comb(n,3).
Ogni incontro è una coppia di squadre, e aggancia un numero (n-2)
delle terzine precedenti.
Quindi il numero minimo teorico di incontri è (come ho già detto
in un post precedente)   Comb(n,3)/(n-2)
Facciamo un esempio semplice con 4 squadre A- B- C- D
Abbiamo   Comb(4,3) = 4   gruppi di 3 squadre:
ABC
ABD
ACD
BCD
Il numero minimo teorico di incontri da trovare è:
Comb(4,3)/(4-2) = 2
Infatti, in questo caso (e solo in questo di 4 squadre) dividendo le
4 squadre in 2 gruppi di 2 squadre ciascuno e facendole incontrare:
Es. A contro B   e C contro D
( ma anche AC  e BD , oppure infine AD  e BC )
si ottiene con 2 partite quello che si desiderava.
Meno di 2 partite è matematicamente impossibile, e questa è la
dimostrazione che dividendo in 2 gruppi omogenei si realizza il
minimo.
Vediamo 6 squadre: ABCDEF
N. teorico = Comb(6,3)/(6-2) = 5 incontri
N. pratico = n(n-2)/4 = 6  incontri
e precisamente:  AB   AC   BC    :     DE    DF    EF
7 squadre: ABCDEFG
N. teorico = 35/5 = 7   incontri
N. pratico = (7-1)^2/4 = 9  incontri
e precisamente:  AB   AC   AD   BC   BD   CD     EF    EG    FG
Ecc.  Ecc......
Nino 

e precisamente:  AB   AC   AD   BC   BD   CD     EF    EG    FG
E qui dimostri che potrebbero essere 7, ma ti accontenti di 9.  Cioè il
minimo calcolato in quel modo ti dice solo che forse si può fare di
meglio, e quindi non serve a dimostrare che quello che hai trovato è il
vero minimo.

 che non si può, ma non vedo la dimostrazione.
Il requisito minimo e' che tutte le squadre incontrino tutte le altre 
meno una, ma non sarebbe un girone bilanciato. Se le incontrassero tutte 
meno due (o meno piu' di due) il sorteggio delle tre squadre potrebbe 
prenderne tre che non si sono mai incontrate.


Ma questo dimostra che dimezzando le squadre in due gruppi,
quando si tende al minimo possibile (4 squadre) i due minimi
(teorico e reale pratico) coincidono. Poi, crescendo il campo
(aumentando il numero delle squadre) i due valori necessariamente
si discostano.
Es. 5 squadre  ABCDE
N. teorico= Comb(5,3)/(5-2) = 10/3 = 3,3....
N. pratico= 4     AB  AC  BC  DE  (non può essere un dato
frazionario!!!!)
Se uno non si convince, non so più che dire...


:

Questo è vero se assumi che il girone abbia una qualche simmetria, non
in generale.  Per esempio, con cinque squadre, il minimo a due gironi è
4.  A un girone, il minimo come dici tu sarebbe 5*(5-2)/2, quindi 8.  Ma
in realtà si può fare con 5:
ab
bc
ca
ad
de
La mia questione è: qual è il minimo a un girone?  Se risolviamo questa,
si può confrontare col minimo a due gironi che abbiamo già, e siamo a
posto.
Comunque per me basta, io non ci penso più :)

 ad
Questa partita serve solo per lo spettacolo... :-)

Questa partita serve solo per lo spettacolo... :-)
No, la partita in pių del minimo serve a far sė che sia un girone solo,
e non due.

 e non due.
Non ci siamo...
Anche con un girone solo devi scegliere il minimo delle partite
necessarie.
Quella è semplicemente SUPERFLUA, qundi non c'è ragione
di giocarla.
Non è possibile realizzare quello che si desidera (senza aggiungere
partite inutili) se non si dividono le squadre in due gironi: se questi
sono composti dallo stesso numero di squadre (o circa per i dispari)
si raggiunge il minimo; altrimenti, la soluzione c'è ancora, ma il
risultato non è ottimale.
Guarda il tuo esempio delle 10:57 e ti accorgerai di aver diviso
le 5 squadre in 3+2 (anche se poi hai aggiunto una partita inutile) 

 E qui dimostri che potrebbero essere 7, ma ti accontenti di 9.  Cioè il
idem come sopra.

 posto.
e si, ma le squadre erano 16:-)

squadre a caso almeno 2 si siano incontrate (elimini la partita EF 
No, ce ne vogliono 6.  Se elimini EF e prendi la terna E, F, A, nessuna
di queste si è incontrata.

:

Io parlavo del minimo a un girone per un numero qualunque di squadre.  E
per spiegare il concetto ho fatto l'esempio con poche squadre.

 per spiegare il concetto ho fatto l'esempio con poche squadre.
Va bene... <:-(  allora non hai capito che NON è possibile risolvere il
problema se non si fa (anche idealmente) la suddivisione in due gruppi
di squadre disgiunti. Ovvio che, se vuoi, puoi anche inframmezzare delle
partite, ma sarebbero SUPERFLUE per quello che si vuole ottenere. 

 idem come sopra.
No. Servono proprio tutte e 9. La spiegazione è che ci sono 
rappresentatività
ripetute. Es. ABC   viene coperto sia dalla partita AB, che dalla AC, che
dalla BC.  La conseguenza è che questa ridondanza produce inevitabilmente
altre lacune, che devono essere coperte con partite supplementari, in numero
complessivamente superiore a quello che dà il calcolo teorico. 

partite, ma sarebbero SUPERFLUE per quello che si vuole ottenere. 
Boh.  L'ho già detto, ma lo ripeto.  Che la soluzione sia dividere in
due gironi sono convinto anch'io.  Ma tra essere convinti e dimostrare
c'è una differenza.  Io penso che la dimostrazione non sia semplice, e
come dicevo ho rinunciato a cercarla, ma magari invece è semplice,
chissà.
Per chiarire il concetto, ci sono state tante congetture anche
semplicissime da esprimere, sui numeri interi, di cui tutti i matematici
del mondo sono convinti e che addirittura usano come ipotesi, ma non
sanno dimostrare.  Alcuni di questi problemi hanno resistito per decenni
o secoli, e benché tutti conoscessero la soluzione nessuno sapeva
dimostrarla.

 dimostrarla.
Su questo siamo d'accordo.
Però, dimostrazioni di questo tipo non riguardano, secondo me, il problema
in questione.
Ricordando sempre che è solo una opinione  :-| 

si fa una divisione in due gironi (o effettiva o anche solo mentale.
Sì, intuitivamente lo vedo anch'io.  Ma non so dimostrare che con un
girone è sempre peggio.