Disuguaglianze e Combinatoria Advanced
Lezione del 02/02/2011
Stage di Massa Progetto Olimpiadi
Disuguaglianze
Colorazioni
• Quando abbiamo a che fare con grafi, tabelle, scacchiere, è utile ricorrere alle “colorazioni”
• ES: da una scacchiera standard 8x8 si tolgono la casella in un angolo e quella opposta. È possibile ricoprire ora la scacchiera con tasselli 2x1?
• NO, in quanto colorando “a scacchiera” tali
tasselli occupano sempre una casella bianca e una nera, quindi il ricoprimento può essere
possibile solo se le caselle nere sono in numero uguale a quelle bianche, ma nel nostro caso
abbiamo tolto 2 caselle dello stesso colore.
Un commesso viaggiatore deve girare tutte le città della regione partendo da A e tornando ad A. I collegamenti in linea continua sono le ferrovie e il biglietto costa 150 euro, i collegamenti tratteggiati sono gli aerei e costano 250 euro.
Quanto spenderà al minimo il commesso viaggiatore?
Invarianti
• L’invariante è una quantità che non cambia
• Esempio: su una lavagna sono scritti 10
numeri. Ad ogni turno si aggiunge 1 ad un numero e si toglie 1 da un altro. Invariante:
somma dei numeri
• Esempio: su una lavagna sono scritti 10
numeri. Ad ogni turno si aggiunge o si toglie 1 da 2 numeri. Invariante: parità della somma dei numeri.
• Esercizio di esempio:
• Ci sono 3 scatole contenenti molte palline. Ad ogni mossa si può o togliere una pallina da
ogni scatola o prendere 2 palline da una
scatola e metterne una in ciascuna delle altre due. Qual è l’invariante?
• Antonio e Bernardo giocano al seguente gioco:
sono date due pile di gettoni, una con m gettoni e l'altra con n gettoni. Ogni giocatore sceglie a
turno una delle seguenti mosse:
• prendere un gettone da una delle pile;
• prendere un gettone da ciascuna delle pile;
• spostare un gettone da una pila ad un'altra.
• Perde chi non può più muovere. Comincia
Antonio. Determinare, in funzione di m ed n, se uno dei due giocatori ha una strategia vincente, e in caso affermativo specicare di quale giocatore si tratta.
• Nel paese di cuccagna si gioca al seguente
solitario. Si parte da una stringa di zeri ed uni, e si possono effettuare le seguenti mosse:
• Cancellare due uni consecutivi
• Cancellare tre zeri consecutivi
• Sostituire una sequenza 01 con 100
• Si vince se si riesce a ridurre la stringa ad una formata da due cifre o meno.
• Quante e quali sono fra tutte le 1024 stringhe di 10 cifre quelle partendo dalla quali non è possibile vincere?
