Doppio TST anche qui!!!

[Simo_the_wolf]

Ecco i due problemi di combinatoria al TST07

2) In un torneo con $ 2n+1 $ abbiamo che ogni squadra ha giocato una ed una sola volta con tutte le altre. Chiamiamo una terna di squadre $ A,B,C $ ciclica se $ A $ ha battuto $ B $, $ B $ ha battuto $ C $ e $ C $ ha battuto $ A $.

(a) Qual è il numero minimo di terne cicliche?
(b) Qual è il numero massimo di terne cicliche?

4) Dato un grafo completo con $ n $ vertici, vogliamo colorare vertici e lati in modo che tutti i lati uscenti da un vertice siano di colore diverso tra loro e diversi dal vertice stesso. Qual è il numero minimo di colori che dobbiamo usare?

[moebius]

Ok... rompo il ghiaccio? Credo di non stupire nessuno dicendo che il minimo è 0!
Per il resto... Ehm... Esiste un teoremone di teoria dei grafi oppure la soluzione si fa a manina? Perchè nel secondo caso, io ne avrei una ma il risultato è... come dire... un pò pilotato...
Se esiste una dimostrazione cool manco provo a sistemarla... altrimenti... Oh my god!

[Boll]

Tutta a manina tranquilla tranquilla...

[moebius]

....
Per autoflagellarmi scriverò 1000 volte:
"La somma dei quadrati di n numeri con somma fissata è minima quando sono tutti uguali e non il contrario!!!!" (*)
Btw...
A me viene che sono al massimo $ \frac{2n^3+3n^2+n}{6} $...
Per 1 funziona (viene 1), funziona per 2 (viene 5) quindi funziona!
Scherzi apparte... Poichè sono dispari ce la faccio a farne esattamente $ \frac{2n^3+3n^2+n}{6} $. Perchè? Vedi (*)
Se è giusto con un pò di calma dopo pranzo scrivo anche uno straccio di delirio di dimostrazione

[claudiothe2nd]

come mai avete snobbato il primo problema?? perchè troppo facile?

cmq nelle partite sono ammessi i pareggi? perchè in tal caso il numero minimo di terne cicliche è palesemente 0...

per il numero massimo invece prenderei una terna casuale e calcolerei la probabilità che sia ciclica, per poi moltiplicare il risultato con il numero di terne possibili...
lo svolgimento numerico deve attendere una risposta per la questione dei pareggi...

[moebius]

Dunque... io ho considerato che non fossero ammessi pareggi... ed anche in quel caso il minimo secondo me è 0....
Ehm... quale sarebbe il primo problema? Perchè a questo io avrei risposto
Per la seconda domanda, non ho capito cosa cambi... Ti viene chiesto il numero massimo di terne cicliche possibili. Ogni terna ciclica non ha "pareggianti" by definition. Oppure: supponiamo che esista una configurazione che realizza il massimo di terne cicliche in cui qualche squadra ha pareggiato; se sostituisci il pareggio con la vittoria di una delle due il numero di terne cicliche può solo aumentare... so...
Infine: l'osservazione sulla probabilità non sta ne in cielo ne in terra secondo me
Bye
P.S.: Rileggendo l'ultima frase mi è sembrato che potesse risultare offensiva... ti assicuro che non volevo in nessun caso esserlo... spero che la faccina si capisca, altrimenti mi toccherà mettere un video di me mentre scrivo

[claudiothe2nd]

la probabilità nel senso del rapporto di terne cicliche su terne non cicliche...no?

A me viene che sono al massimo $ \frac{2n^3+3n^2+n}{6} $...
Per 1 funziona (viene 1), funziona per 2 (viene 5) quindi funziona!

cmq facendo uno schemino con cinque squadre, a me vengono 10 terne cicliche, come la mia formulina: [4(n^3) - 2n]/3; l'ho ricavata, semplicemente osservando che prendendo tre squadre, qualsiasi siano, riesco comunque a metterle nell'ordine "ciclico". Quindi le terne sono le combinazioni semplici.
ovviamente se non ci sono pareggi...

@moebius: non riesco a seguire i tuoi ragionamenti, quindi è anche possibile che io abbia frainteso il problema...

[Sisifo]

osservando che prendendo tre squadre, qualsiasi siano, riesco comunque a metterle nell'ordine "ciclico".

Hmm.. scusami ma questa è una bojata.. Se tu hai tre squadre A, B, C tali che A ha battuto B, A ha battuto C e B ha battuto C non so proprio come potresti riuscire a metterle nell'ordine ciclico..

(sì, anche nel caso migliore trovi situazioni di questo genere..)`

[claudiothe2nd]

oops! ho tralasciato la condizione che C debba aver battuto A!!!

...avevo detto che era possibile una mia incomprensione del problema...mi sembrava infatti troppo 'na cazzata..

I'm sorry..