SSSUP 2009 n 3: tessere del domino

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

SSSUP 2009 n 3: tessere del domino

Messaggio da mrossi » 12 set 2009, 15:56

Pincopallino ha a disposizione 21 tessere di domino in cui su ciascuna metà sono presenti da 0 a 5 puntini. Per ciascuna combinazione di puntini esiste una sola tessera, che può essere impiegata in entrambi i versi (ad esempio $ 35 $o $ 5 3 $).

Pincopallino dispone le tessere in fila in modo che vengano rispettate le seguenti regole:
a) I lati adiacenti di due tessere hanno lo stesso numero di puntini
b) Il primo e l'ultimo lato della fila hanno lo stesso numero di puntini.

Un esempio di fila può essere:

$ 0 1 |1 2 | 2 3 | 3 3 | 3 0 $

a) Qual è il numero massimo di tessere che può mettere in fila?
b) Qual è il numero massimo di tessere che può mettere in fila se i puntini fossero da 0 a 2009?

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 16 set 2009, 13:27

già fatto a Pisa durante il senior..

quesito bonus) Qual è il numero massimo di tessere che può mettere in fila se i puntini fossero da 0 a n?
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 16 set 2009, 13:46

Io avevo pensato che il numero di volte che un certo numero di puntini compare nella sequenza è pari (visto che devono sempre essercene due vicini e il primo e l'ultimo sono uguali), mentre sommando tutti quelli che ci sono in tutto nelle tessere sono dispari. Quindi bisogna togliere una tessera contenente ciascun numero quindi nel caso di da 0 a 5 almeno 3 tessere, per da 0 a 2009 sono 1005.

Poi con 5 bastava un esempio per far vedere che con 21 - 3 = 18 tessere è possibile, mentre per gli altri casi immagino ci vorrà una regola per costruire la sequenza.

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 16 set 2009, 21:57

la risposta è giusta... ma come si dimostra? :wink:
induzione
e per n generale? la regola è la stessa?
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 17 set 2009, 17:39

Purtroppo non riesco a dimostrare la mia risposta.

Comunque per n generico c'è differenza per n dispari e n pari.
Infatti, ogni numero di puntini compare in totale sulle varie tessere n + 2 volte. Per n pari quindi ciascun numero compare un numero pari di volte, quindi si può formare una sequenza con tutte le tessere, che sono (questo si dimostra facilmente)

$ \displaystyle \frac {(n+1)(n+2)}{2} $

Con n dispari invece bisogna togliere tessere in modo che ogni numero di puntini compaia in totale un numero pari di volte. Il numero minimo di tessere rimosse si ha togliendo le tessere 01, 23, 45, ..., n-1 n, che sono $ \frac{n+1}{2} $.

Quindi la sequenza in questo caso è composta al massimo da
$ \displaystyle \frac {(n+1)(n+2)}{2}-\frac{n+1}{2}= \frac {(n+1)^2}{2} $

Mi rimane sempre da dimostrare che una sequenza con questo numero massimo di tessere è fattibile, e non riesco a capire come farlo per induzione... Un altro suggerimento?

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 17 set 2009, 17:58

HINTONE
se parti dal caso 0123, puoi costruire la sequenza in questo modo:
togli 01 23 e poni
00|02|21|13|30 (ovviamente le tessere doppie 11,22,33 si possono comunque mettere..)
se adesso vai al caso 012345, ti accorgi che puoi continuare la sequenza precedente, mettendo tutte le tessere in più dopo 30 scartando la tessera 45
se generalizzi per n e n+2 (dove n indica il più grande numero presente sulle tessere) trovi che per n pari, non c'è bisogno di togliere tessere, mentre, per n dispari, esiste sempre una configurazione che ti permette di mettere tutte le tessere, meno quelle scartate
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 18 set 2009, 11:30

Eh avevo notato anche questo, però non riesco a stendere una dimostrazione rigorosa nel caso generico con n, n+2...

antosecret
Messaggi: 214
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da antosecret » 18 set 2009, 12:45

EDIT: ho trovato una imprecisione nella dimostrazione quindi preferisco riscriverla. grazie mrossi.
Ultima modifica di antosecret il 18 set 2009, 14:50, modificato 3 volte in totale.
Dirty Physician!!!! (senza offesa per i farmacisti, ovviamente) :-)

mrossi
Messaggi: 58
Iscritto il: 31 lug 2009, 16:07

Messaggio da mrossi » 18 set 2009, 12:56

antosecret ha scritto: Allora possiamo, scelto un numero k a caso, prendere 2 tessere che hanno il numero k (ad esempio la hk e la jk) e sostituirle con la tessera jk (presa dalla scatola)
mhmh non credo di aver capito :?

antosecret
Messaggi: 214
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da antosecret » 18 set 2009, 15:18

Supponiamo di aver già eliminato le tessere superflue in maniera che ogni numero compaia solo un numero pari di volte.
Voglio dimostrare che è possibile creare una catena composta da tutte queste tessere.

Per farlo scegliamo una tessera $ $ab $ a caso e cominciamo ad aggiungere tessere (ad esempio) sul lato $ $b $. Poichè ogni numero compare un numero pari di volte, riusciremo ad aggiungere tessere a questa catena (sempre dal lato di $ $b $) fino a chè non gli attacchiamo l'ultima tessera con un estremo $ $a $ disponibile (ciò perchè l'altra tessera con l'estremo $ $a $ sta all'inizio della catena). Se a questo punto le tessere sono finite abbiamo vinto.
Se no, scegliamo una tessera $ $jk $ a caso tra le rimanenti. Poichè tutte le tessere che contengono la $ $a $ sono già nella catena, tale catena contiene in particolare la tessera $ $aj $. stacchiamo allora la catena in corrispondenza della tessera $ $aj $ e attacchiamo la seconda parte della catena (che finisce con $ $a $) all'inizio della stessa:
$ $ax-_{\dots} -aj-jz-_{\dots} -ya \,\,\,\,\rightarrow \,\,\,\, jz-_{\dots} -ya-ax-_{\dots} -aj $
Poi attacchiamo la nostra tessera j-k alla fine della catena:
$ $jz-.....-jk $
A questo punto nella catena compaiono solo un numero dispari di numeri $ $k $ e quindi possiamo (come sopra) continuare ad aggiungere tessere fino a che non attacchiamo alla catena l'ultima tessera che contiene la $ $j $.
Infine basta riapplicare questo ragionamento fino a chè non abbiamo piazzato tutte le tessere.

Spero sia più chiaro (e più corretto) di prima...
Dirty Physician!!!! (senza offesa per i farmacisti, ovviamente) :-)

Rispondi