48. Scacchi
48. Scacchi
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
LTE4LYF
Re: 48. Scacchi
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}$
$\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}$
Re: 48. Scacchi
Però non mi sembra così scontato dalla tua soluzione che quello sia proprio il massimo. Mi sfugge qualcosa?
"We' Inge!"
LTE4LYF
LTE4LYF
Re: 48. Scacchi
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?)
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?)
-
- Messaggi: 30
- Iscritto il: 02 feb 2014, 19:23
- Località: Napoli
Re: 48. Scacchi
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
$ \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
Re: 48. Scacchi
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.
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
LTE4LYF
-
- Messaggi: 30
- Iscritto il: 02 feb 2014, 19:23
- Località: Napoli
Re: 48. Scacchi
Credo che dicendo che diminuisce se accade quella cosa una volta, se accade la seconda diminuisce ancora di più, e così via, no?
Re: 48. Scacchi
Quello che non mi tornava tanto era il fatto che tu dovessi sempre togliere $n$, magari ne devi togliere di meno.
"We' Inge!"
LTE4LYF
LTE4LYF
-
- Messaggi: 30
- Iscritto il: 02 feb 2014, 19:23
- Località: Napoli
Re: 48. Scacchi
No perchè quei due giocheranno al massimo $ n $ partite in totale.
Re: 48. Scacchi
Boh comunque sia è già passata una settimana, quindi procedi pure col nuovo problema
"We' Inge!"
LTE4LYF
LTE4LYF