Scacchiera russa

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Scacchiera russa

Messaggio da Triarii » 14 apr 2014, 17:16

Da una griglia $20\times 20$ sono rimossi $20$ rettangoli di dimensioni $1\times 20$, $1\times 19$,... $1\times 1$, dove i lati dei rettangoli giacciono sulle linee della griglia. Mostrare che possono essere rimossi almeno $85$ rettangoli $1\times 2$ dalle caselle restanti.
"We' Inge!"
LTE4LYF

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Scacchiera russa

Messaggio da simone256 » 15 apr 2014, 13:08

$ 300 $

Domandina:
Poter togliere i rettangoli significa che possiamo individuarli o significa che possiamo effettivamente toglierne 85?
Esempio: Se ho la tipica L formata da 3 caselle isolate dalle restanti caselle rimaste, viene considerata come due possibili pedine 1*2??
Giudicando dall' "almeno" e dai dati penso proprio di sì... Ma meglio esserne sicuri perchè non sarebbe la prima caspiata che sparo :P
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Scacchiera russa

Messaggio da Triarii » 15 apr 2014, 19:20

Questo è quel problema che ti dicevo che non avevo risolto e di cui non ho la soluzione... Comunque io l'avevo interpretato che devono esistere contemporaneamente le pedine che rimuovi, quindi nel caso della forma a "L" posso levarci solo 1 tassellino $2\times 1$.
Può darsi che però l'abbia interpretato male io!
"We' Inge!"
LTE4LYF

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Scacchiera russa

Messaggio da simone256 » 15 apr 2014, 22:07

Perchè i 20 rettangoli che si tolgono complessivamente tengono 210 quadretti, e togliendo 85 pedine se ne arrivano a togliere altri 190 di quadretti... Quindi in totale si tolgono 400 quadretti (tutti). Quindi se c'è scritto "almeno" 85 pedine mi fa pensare che se ne possono togliere di più... E che quindi questa sia la via sbagliata e che le pedine non devono essere necessariamente tolte contemporaneamente. Che ne pensi? :)
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

Avatar utente
karlosson_sul_tetto
Messaggi: 1441
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Scacchiera russa

Messaggio da karlosson_sul_tetto » 15 apr 2014, 22:14

$85\cdot 2=170$
Mi sa che hai fatto un approssimazione con un errore abbastanza grande :lol:
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Scacchiera russa

Messaggio da simone256 » 15 apr 2014, 22:20

HAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHA
Suvvia non demigrate i fisici ora :roll:
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Scacchiera russa

Messaggio da xXStephXx » 16 apr 2014, 19:33

Intanto qui si può vedere che suddividendo la griglia in quadratini $2 \times 2$ (e ce ne sono $100$) sicuramente se un quadratino viene coperto da un solo tassello è ancora possibile estrarre un rettangolo $2 \times 1$ da esso. Quindi per sprecare un quadratino $2 \times 2 $ bisogna coprirlo con almeno due tasselli.
Adesso si nota che i pezzi da $20,19,18$ possono passare al massimo per $10$ quadratini diversi. Il pezzo da $17$ e quello da $16$ massimo per $9$ quadratini e così via scendendo di uno ogni due.... il pezzo da $1$ può coprire al massimo un quadratino. La speranza è che questa somma faccia $115$, che vorrebbe dire che posso estrarre almeno $85$ rettangoli $2 \times 1$ dallo spazio rimanente... Purtroppo quella somma fa $119$ :roll: quindi ne riesco ad estrarre solo $81$ :cry:

Ma siccome in questo thread ci sono soprattutto fisici e astronomi si può concludere che $81 \simeq 85$... oppure ingegnarsi a trovare qualche trucco migliore... :D

Rispondi