La solita scacchiera $m \times n$

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

La solita scacchiera $m \times n$

Messaggioda Gerald Lambeau » 10/08/2015, 14:41

Own (o quasi).
Sia data una scacchiera $m \times n$ con $m, n$ interi $ \ge 1$. Viene tolto un quadratino qualsiasi della scacchiera e d'ora in avanti l'area di quel quadratino sarà considerata esterna alla scacchiera.
Determinare (ovviamente in funzione di $m$, $n$ e del quadratino tolto) qual è il massimo numero di tasselli $2 \times 1$ (l'equivalente di due quadratini adiacenti della scacchiera) che può essere usato per ricoprire la scacchiera, con le seguenti regole:
- rispettando i bordi dei quadratini della scacchiera;
- senza che i tasselli si sovrappongano;
- senza uscire dalla scacchiera (e quindi anche senza entrare nell'area del quadratino tolto).
Enjoy!
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: La solita scacchiera $m \times n$

Messaggioda Giovanni98 » 10/08/2015, 23:06

Non capisco il fatto del massimo numero di tasselli, cioè se è possibile ricoprire una scacchiera con quelle condizioni con tasselli da $2\times1$ il numero di tasselli é fissato a $\frac {mn - 1}{2}$. Ad ogni modo, una scacchiera é ricopribile se e solo se $m$ ed $n $ sono dispari poiche se uno fra $m,n $ è pari ho che $mn - 1$ è dispari ; e se colorando la nostra scacchiera nella maniera usuale il quadratino tolto è di colore nero poiché in ogni scacchiera con $m,n $ dispari il numero di caselle nere è maggiore di quello delle caselle bianche di 1 e poichè ogni tassello $2\times1$ copre esattente una casella nera e una bianca.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: La solita scacchiera $m \times n$

Messaggioda Gerald Lambeau » 11/08/2015, 13:38

Non hai capito il concetto di massimo: se almeno uno fra $m$ e $n$ è pari togliendo un quadratino ottieni un numero di quadratini dispari che non puoi ricoprire tutto, quindi ci deve essere un massimo numero possibile di tasselli, minore di $\frac{mn-1}{2}$, che puoi usare; per forza di cose resterà fuori almeno un altro tassello.
Per $m$ e $n$ dispari è giusta, ma ti invito a trovare una condizione ottimale che ti permetta di arrivare a quel massimo. E se hai capito cosa intendo per massimo prova anche il caso $m$ e $n$ dispari e quadratino tolto bianco, il problema originale da cui ho preso spunto era così.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: La solita scacchiera $m \times n$

Messaggioda Giovanni98 » 11/08/2015, 15:37

Capito, riproverò a breve.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: La solita scacchiera $m \times n$

Messaggioda Gerald Lambeau » 30/08/2015, 22:09

Ancora nessuno? So che come problema non è un granché e mi scuso per il fatto che si faccia con sola casistica, ma provateci, dai!
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite