Pulci su scacchiera

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

Pulci su scacchiera

Messaggioda xXStephXx » 15/12/2013, 21:18

Abbiamo una scacchiera [tex]8 \times 8[/tex]. Su ogni casella c'è una pulce. A un certo punto ogni pulce fa un salto in una casella adiacente. Quante possono essere al massimo le caselle libere?
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Pulci su scacchiera

Messaggioda Xeanort » 15/12/2013, 21:32

Concentrandosi su 3 tre file le celle libere sarebbero 40, che dovrebbe essere il massimo. Giusto?
Avatar utente
Xeanort
 
Messaggi: 110
Iscritto il: 27/11/2013, 17:58

Re: Pulci su scacchiera

Messaggioda xXStephXx » 15/12/2013, 21:44

Si può far di meglio xD
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Pulci su scacchiera

Messaggioda Livex » 15/12/2013, 21:48

le caselle in diagonale sono adiacenti?
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: Pulci su scacchiera

Messaggioda xXStephXx » 15/12/2013, 22:16

No xD Solo in alto, in basso, a destra e a sinistra.
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Pulci su scacchiera

Messaggioda Livex » 15/12/2013, 22:40

posso affermare con una certa certezza che le caselle libere rimaste possono essere al massimo 48
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: Pulci su scacchiera

Messaggioda xXStephXx » 15/12/2013, 23:01

Dimostra questa certezza xD
E in caso ciò non basta a dire che è il massimo (sempre se lo è)
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Pulci su scacchiera

Messaggioda Livex » 15/12/2013, 23:28

Intanto dico che il problema equivale a tassellare completamente una scacchiera 8 x 8 con delle croci (una parte delle croci puo anche uscire dalla scacchiera e sovrapporsi con altre croci) e con il minor numero di pezzi possibile.

Voglio dimostrare che il numero di croci (pezzi) minimo è 16 (e sono comunque sufficienti, ho fatto la prova).

Siccome le croci occupano 5 caselle e la scacchiera ha 64 caselle, devono esserci almeno [tex]13[/tex] croci ([tex]5 \cdot 13=65)[/tex].

E provo a concludere domani, devo fare un po di disegni e di colorazioni.
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: Pulci su scacchiera

Messaggioda lorenzocollodi » 16/12/2013, 14:08

ma se è 8x8 solo quelle "sul bordo" possono uscire e lasciare una casella libera, quindi sono 8+8+6+6 che sono 28, o non ho capito bene il testo?
lorenzocollodi
 
Messaggi: 49
Iscritto il: 27/11/2013, 15:35

Re: Pulci su scacchiera

Messaggioda xXStephXx » 16/12/2013, 15:14

@lorenzocollodi: nessuna pulce può uscire dalla scacchiera. Saltare su una casella adiacente implica anche non poter uscire fuori :D
@Livex: non ho ben capito il tuo procedimento... però ti anticipo che non penso che sia riuscito davvero a lasciare [tex]48[/tex] caselle libere xD
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite