48. Scacchi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

48. Scacchi

Messaggio da Triarii »

Ad un club di scacchi, i giocatori possono giocare fra di loro oppure contro un computer. Ieri c'erano $n$ giocatori al club. Ogni giocatore ha giocato al più $n$ partite, ed ogni coppia di giocatori che non hanno giocato fra di loro ha giocato al massimo $n$ partite in totale. Dimostrare che ieri sono state giocate al più $\dfrac {n(n+1)} {2}$ partite
"We' Inge!"
LTE4LYF
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 48. Scacchi

Messaggio da nassus95 »

Scusami ma forse ho capito male il problema. Il massimo delle partite giocate le ho quando ogni giocatore gioca $n$ partite e ciò è possibile quando tutti giocano con tutti gli altri $n-1$ giocatori (quindi $\frac{n(n-1)}{2}$ partite) e tutti giocano una partita con il computer (quindi $n$ partite).
$\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}$
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 48. Scacchi

Messaggio da Triarii »

Però non mi sembra così scontato dalla tua soluzione che quello sia proprio il massimo. Mi sfugge qualcosa?
"We' Inge!"
LTE4LYF
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 48. Scacchi

Messaggio da nassus95 »

in effetti...
Allora mi sorge un dubbio: un giocatore può giocare con un altro o con il computer più di una volta? (ovvero due giocatori possono fare assieme 2,3,.. partite? e con il computer?)
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: 48. Scacchi

Messaggio da lucaboss98 »

Assumiamo che ci sia stato anche una sola partita fra una coppia di giocatori mai svoltasi poichè diciamo che hanno giocato entrambi contro il computer, allora le partite sarebbero
$ \dfrac{n^2+n+4}{2} $ , che è maggiore, ma non è così perchè quei due giocatori non si sono mai sfidati e quindi la somma del numero delle partite giocate da ognuno deve essere al più $ n $ , ma nel caso $ \dfrac{n^2+n+4}{2} $ sarebbero state giocate da entrambi $ n $ partite, quindi $ 2n $ , allora va sottratto $ n $. Allora abbiamo $ \dfrac{n^2+n+4}{2} -n = \dfrac{n^2-n+4}{2} ≤ \dfrac{n(n+1)}{2} $ per ogni $ n≥2 $ (il caso un solo giocatore è ovvio, quindi tralascio) . Se ancora meno avversari si sono sfidati viene analogamente seguendo lo stesso ragionamento.
Assumiamo ora che l'opposto, quindi che due avversari si sono sfidati più di una volta. Abbiamo due casi:
i) Entrambi non hanno giocato con il computer.
ii) Entrambi non hanno giocato con altri giocatori.
Caso i) è banale in quanto si viene a giocare una partita in meno e quindi le partite sono $ \dfrac{n(n+1)}{2}-1=\dfrac{n^2+n-2}{2}<\dfrac{n(n+1)}{2} $
Caso ii) Chiamiamo $ A $ e $ B $ i due che si risfidano, e rispettivamente $ C $ e $ D $ quelli che avrebbero dovuto sfidare. Abbiamo che si gioca una partita in meno a meno che $ C $ e $ D $ non si risfidano, raggiungendo sempre $ \dfrac{n(n+1)}{2} $ e quindi non di più (si, sto tralasciando che in realtà sono meno, ma serve dimostrare che non supera tale numero, quindi va bene).
Spero di essere stato chiaro e che sia corretta :D
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 48. Scacchi

Messaggio da Triarii »

Premetto che
a) Non ho la soluzione ufficiale
b) La mia probabilmente è sbagliata (quindi sono stato un idiota a proporre questo problema per la staffetta)
Comunque non mi è chiaro il passaggio in cui sottrai $n$ partite e poi dici che funziona così anche se levo altre partite.
"We' Inge!"
LTE4LYF
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: 48. Scacchi

Messaggio da lucaboss98 »

Credo che dicendo che diminuisce se accade quella cosa una volta, se accade la seconda diminuisce ancora di più, e così via, no?
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 48. Scacchi

Messaggio da Triarii »

Quello che non mi tornava tanto era il fatto che tu dovessi sempre togliere $n$, magari ne devi togliere di meno.
"We' Inge!"
LTE4LYF
lucaboss98
Messaggi: 30
Iscritto il: 02 feb 2014, 19:23
Località: Napoli

Re: 48. Scacchi

Messaggio da lucaboss98 »

No perchè quei due giocheranno al massimo $ n $ partite in totale.
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 48. Scacchi

Messaggio da Triarii »

Boh comunque sia è già passata una settimana, quindi procedi pure col nuovo problema ;)
"We' Inge!"
LTE4LYF
Rispondi