Cesenatico 1995 1

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Cesenatico 1995 1

Messaggioda Rho33 » 27/02/2016, 15:27

Determinare per quali valori dell'intero [tex]n[/tex] è possibile ricoprire, senza sovrapposizioni, senza lasciare caselle vuote e senza fare sporgere tasselli, un quadrato di lato [tex]n[/tex] con tasselli del tipo mostrato in figura(allegato), dove ogni quadratino del tassello ha lato unitario.
Non hai i permessi necessari per visualizzare i file allegati in questo messaggio.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Cesenatico 1995 1

Messaggioda carlotheboss » 27/02/2016, 17:01

Abbastanza "sperimentale":
Testo nascosto:
Per tutti i quadrati con lato multiplo di [tex]6[/tex] (escludendo chiaramente 0) poiché vedo che posso coprire un quadrato [tex]6 \times 6[/tex] usando 4 pezzi e scompongo qualunque altro quadrato con lato divisibile per 6 in tanti quadratini 6x6. Inoltre noto che ogni lato del quadrato può essere "coperto" solo da blocchi con al margine 1 o 5 quadratini. Inoltre, supponiamo di considerare il lato a sinistra, per coprirlo senza fare sporgere a sinistra alcun quadratino devo alternare facce da 1 e da 5 (si vede subito provando a mano). Dunque ogni lato sarà costituito da blocchi con basi di 5 e 1 alternati (per spiegarmi meglio, se un lato ha [tex]k[/tex] basi da 5 deve avere un numero di basi da 1 tra [tex]k-1[/tex] e [tex]k+1[/tex]). Chiaramente l'area del quadrato deve essere divisibile per 9 dunque [tex]3 | n[/tex] e quindi le facce da 5 e da 1 devono per forza essere lo stesso numero su un lato, che viene pertanto multiplo di 6.
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Cesenatico 1995 1

Messaggioda Rho33 » 27/02/2016, 18:26

Allora, il risultato a cui sei pervenuto è giusto. Il punto è che non hai spiegato perchè il caso dispari non è valido, ad esempio perchè per [tex]n=9,15,21 ...[/tex] non funge (oppure, cosa più probabile, non lo ho capito io :lol: ). In caso volessi vedere cosa intendo, ho postato la mia dimostrazione in "Stile dimostrativo- Combinatoria".
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Cesenatico 1995 1

Messaggioda carlotheboss » 27/02/2016, 18:41

In realtà l'ho spiegato (male evidentemente lol):
Testo nascosto:
se provi a disegnare mano a mano è molto, ma molto, più evidente di quanto possa rendere la mia dimostrazione a parole, probabilmente ci sono modi più formali D:
il punto è che ogni lato del quadrato può essere solo "ricoperto" usando o la parte da 5 o quella da 1 del "coso" (sono le due basi estreme). Dunque posso dire [tex]n = 5k + j[/tex]. Ora consideriamo, WLOG, il lato sinistro, che vogliamo coprire senza far sbucare quadratini a sinistra di esso. Notiamo che non è possibile accostare due basi da 5 (sempre tenendo i cosi orientati allo stesso modo) poiché mi si formerebbe uno spazio di 2 quadratini alla riga dopo, tra le due righe di 3, che non è possibile riempire (non posso attaccare due basi da 1 per la forma del coso). Inoltre non è nemmeno possibile accostare le due basi da 1 (incorrerei nello stesso problema, mi si formerebbe una lacuna che non potrei tappare).
A questo punto l'unico modo che ho per ricoprire il lato è alternare basi da 5 e da 1 (un esempio di lato può essere 51515 o 151), dunque, con la notazione precedente [tex]j[/tex] (il numero di basi da 1 usate) non può differire per più di 2 da [tex]k[/tex] (il numero di basi da 5 usate).
Ora considero l'area del quadrato: essa deve essere divisibile per [tex]9[/tex] dunque [tex]3 | n[/tex]. Consideriamo i 3 casi per [tex]n[/tex]: se [tex]n = 5k + (k-1) = 6k - 1[/tex] non è divisibile per 3, se [tex]n = 5k + (k+1) = 6k + 1[/tex] non è ancora divisibile per 3 e rimane solo [tex]n = 5k + k = 6k[/tex] che è effettivamente divisibile per 3 (ho un numero uguale di basi da 5 e da 1).
Da quest'ultima osservazione noto che gli unici [tex]n[/tex] che posso ricoprire sono i multipli di 6 (quindi è qui che escludo i dispari), che mi basta scomporre in quadrati da [tex]6 \times 6[/tex] che so ricoprire.
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Cesenatico 1995 1

Messaggioda Rho33 » 27/02/2016, 18:51

Ok, ora ho capito! La soluzione è giusta, forse colorare a scacchiera poteva essere una via più formale per arrivare alla conclusione, che ti avrebbe portato facilmente agli assurdi desiderati ;)
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Cesenatico 1995 1

Messaggioda carlotheboss » 27/02/2016, 18:53

Vero anche questo :)
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti