La scacchiera
Avete a disposizione una scacchiera 8 × 8 (come quella della dama o degli scacchi) e 50 pedine.
Volete disporre sulla scacchiera le pedine in modo che:
1) ogni pedina stia esattamente dentro qualche casella e non ce ne sia più di una in ogni casella;
2) coppie di caselle occupate da pedine non abbiano lati in comune (pur potendo avere un vertice
in comune);
3) da qualunque casella rimasta libera si possa raggiungere ogni altra casella libera, solo passando
in verticale o in orizzontale su altre caselle libere, senza scavalcare pedine.
Qual è il massimo numero di pedine che potete disporre sulla scacchiera?
Volete disporre sulla scacchiera le pedine in modo che:
1) ogni pedina stia esattamente dentro qualche casella e non ce ne sia più di una in ogni casella;
2) coppie di caselle occupate da pedine non abbiano lati in comune (pur potendo avere un vertice
in comune);
3) da qualunque casella rimasta libera si possa raggiungere ogni altra casella libera, solo passando
in verticale o in orizzontale su altre caselle libere, senza scavalcare pedine.
Qual è il massimo numero di pedine che potete disporre sulla scacchiera?
Risposte
"simo90":
io ho trovato una configurazioen con 2 pedine in piu'...
Le soluzioni sono tutte e due sbagliate.
si...
Per chi vuole vedere la soluzione è questa:
Comunque provate a spiegare la configurazione che avete trovato. Se anche non è quella ottimale almeno gli altri possono prenderne visione (e cercare di migliorarla) ed è già un passo avanti rispetto al semplice numero
Per chi vuole vedere la soluzione è questa:
Comunque provate a spiegare la configurazione che avete trovato. Se anche non è quella ottimale almeno gli altri possono prenderne visione (e cercare di migliorarla) ed è già un passo avanti rispetto al semplice numero
si ecco e' come quella che avevo trovato io...
piu' che altro bisognerebbe dimostrare che
piu' che altro bisognerebbe dimostrare che
e' il massimo!
@ gian92
se la tua è come la mia, le pedine sono una in meno rispetto alla soluzione di simo16.
se la tua è come la mia, le pedine sono una in meno rispetto alla soluzione di simo16.
"adaBTTLS":
@ gian92
se la tua è come la mia, le pedine sono una in meno rispetto alla soluzione di simo16.
sisi anche io ho trovato la tua configurazione...dico solo che sapendo che tale configurazione con 1 in piu' esiste, ora il problema e' dimostrare che e' il massimo, non tanto trovarla!
sì, certo, anche quello, ma essendo arrivati solo a un numero inferiore, prima che dimostrare che il massimo non è superiore al numero suggerito dall'autore, bisognerebbe anche dimostrare che non è inferiore a tale numero.
questa è con il numero massimo che cercavamo.
la costruzione è quella più immediata, si cerca di massimizzare il bordo, poi le altre sono di conseguenza.
per la dimostrazione mi pare complicato, ci penserò
bello il quesito comunque!
trovata una simile, io invece sono partito dal fatto che ogni pedina che mettiamo ci obbliga a mettere al minimo 2 e al massimo 4 caselle vuote, quindi visto che vogliamo minimizzare le caselle vuote metteremo sicuramente tutte quelle che ci permettono di metterne solo 2 (gli angoli)
quindi siccome sugli angoli ne abbiamo 4, su ognuno dei lati ne possiamo mettere al massimo 2 (oltre agli angoli) perche' abbiamo 4 spazi disponibili e non devono essere consecutive
quindi ce ne possono essere al massiomo 12 sommando quelle su ogni lato
e poi viene fuori quella configurazione
oddio mi e' venuta in mente una idea...
detto $K_n$ il massimo numero di pedine che si possono mettere in una scacchiera $n X n$ in quel modo, che valga $F_n=K_n$
quindi siccome sugli angoli ne abbiamo 4, su ognuno dei lati ne possiamo mettere al massimo 2 (oltre agli angoli) perche' abbiamo 4 spazi disponibili e non devono essere consecutive
quindi ce ne possono essere al massiomo 12 sommando quelle su ogni lato
e poi viene fuori quella configurazione
oddio mi e' venuta in mente una idea...
detto $K_n$ il massimo numero di pedine che si possono mettere in una scacchiera $n X n$ in quel modo, che valga $F_n=K_n$
sono partito esattamente da quel ragionamento, è ciò che intendevo con "massimizzare il bordo".
cosa intendi per $F_n$ ?
cosa intendi per $F_n$ ?
"blackbishop13":
sono partito esattamente da quel ragionamento, è ciò che intendevo con "massimizzare il bordo".
cosa intendi per $F_n$ ?
l'ennesimo numero della sequenza di fibonacci
ho detto una stupidaggine comunque mi sono fatto ingannare dal fatto che $f_8=21$ e che con 1X1 e 2X2 era sempre 1 il massimo...potevo almeno provare con al 3X3 prima di fare una tale ipotesi
già non funziona.
comunque ho provato con le $nxn$ da $1$ a $9$, e mi pare proprio che:
se $n$ è dispari, cioè se è del tipo $n=2k-1$ allora il numero massimo di pedine è $k^2$
invece se $n$ è pari ho tirato fuori una formula empirica, che però credo proprio abbia motivo di funzionare:
$n=2k$ allora il numero massimo di pedine è $k^2+2k-3$ tranne per $n=2$ che è $k^2$ e basta.
comunque ho provato con le $nxn$ da $1$ a $9$, e mi pare proprio che:
se $n$ è dispari, cioè se è del tipo $n=2k-1$ allora il numero massimo di pedine è $k^2$
invece se $n$ è pari ho tirato fuori una formula empirica, che però credo proprio abbia motivo di funzionare:
$n=2k$ allora il numero massimo di pedine è $k^2+2k-3$ tranne per $n=2$ che è $k^2$ e basta.
io avevo risolto il problema "a intuito", cioè senza dimostrare che con più di 21 non si poteva. Però dove ho preso il problema c'è la dimostrazione, quindi se vi interessa posso postarla anche se per ora credo sia meglio di no per permettere a chi vuole provarci di arrivarci da solo 
Risolvere il problema in generale sembra molto interessante, ma non so quanto possa essere difficile...
Risolvere il problema in generale sembra molto interessante, ma non so quanto possa essere difficile...
io avevo trovato questa soluzione
ma è stato fatto di meglio
ma ci sono dei punti, quelli segnati con i puntini in cui le caselle bianche formano dei quadrati quindi sicuramente c'è uno spreco di caselle: infatti i quadrati sono 4 le pedine messe sulla scacchiera sono 17, 17+4 = 21
bisgnerebbe trovare la soluzione per una scacchiera tre per tre 4*4 ecc. per vedere delle analogie
mi sembra che la configurazione massima per una scacchiera con numeor dispari è questa (Esempio 5*5)
$|(-,-,-,-,-),(o, ,o, ,o),(-,-,-,-,-),( , , , , ),(-,-,-,-,-),(o, ,o, ,o),(-,-,-,-,-),( , , , , ),(-,-,-,-,-),(o, ,o, ,o)|$
poi bisogna vedere per un numero pari
"adaBTTLS":
ma è stato fatto di meglio
ma ci sono dei punti, quelli segnati con i puntini in cui le caselle bianche formano dei quadrati quindi sicuramente c'è uno spreco di caselle: infatti i quadrati sono 4 le pedine messe sulla scacchiera sono 17, 17+4 = 21
bisgnerebbe trovare la soluzione per una scacchiera tre per tre 4*4 ecc. per vedere delle analogie
mi sembra che la configurazione massima per una scacchiera con numeor dispari è questa (Esempio 5*5)
$|(-,-,-,-,-),(o, ,o, ,o),(-,-,-,-,-),( , , , , ),(-,-,-,-,-),(o, ,o, ,o),(-,-,-,-,-),( , , , , ),(-,-,-,-,-),(o, ,o, ,o)|$
poi bisogna vedere per un numero pari
ah cmq ho trovato anch'io la soluzione su internet XD
simo90 la soluzione per ogni $n$ credo di averla trovata, l'ho scritta prima..
poi quello che dici sui quadrati nella configurazione di @melia non è corretto, perchè se ci sono 4 caselle libere a quadrato non è detto che tu possa riempirle sempre, infatti nella configurazione non si può in 3 quadrati su 4 , perchè si impedirebbe il passaggio tra le caselle libere.
comunque posta la dimostrazione se ti va, basta che la spoileri.
poi quello che dici sui quadrati nella configurazione di @melia non è corretto, perchè se ci sono 4 caselle libere a quadrato non è detto che tu possa riempirle sempre, infatti nella configurazione non si può in 3 quadrati su 4 , perchè si impedirebbe il passaggio tra le caselle libere.
comunque posta la dimostrazione se ti va, basta che la spoileri.
Questa è la dimostrazione presa dal sito:
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo