In una tabella [tex]5[/tex]x[tex]5[/tex] c'è un [tex]-1[/tex] in una casella ed un [tex]+1[/tex] in tutte le altre.
Una mossa consiste nel cambiare il segno alle caselle di un sottoquadrato [tex]n[/tex] x [tex]n[/tex] con [tex]n \geq 2[/tex].
Per quale posizione del [tex]-1[/tex] iniziale è possibile, tramite mosse legali, ottenere [tex]+1[/tex] in tutte le caselle?
Anche con l'hint non riesco a completare questo esercizio. . Qualcuno può aiutarmi? Grazie.
Esercizio 1.35 da Oliforum allenamento EGMO combinatoria
Re: Esercizio 1.35 da Oliforum allenamento EGMO combinatoria
Prova così: sia [tex]a_{ij}[/tex] la casella di riga [tex]i[/tex] e colonna [tex]j[/tex] ([tex]1\le i,j\le 5[/tex]); definiamo [tex]p[/tex] come il prodotto dei numeri presenti all'interno di tutte le caselle con [tex]j \not = 3[/tex], cosa succede a [tex]p[/tex] quando applichi una qualunque delle mosse legali?
Testo nascosto:
Re: Esercizio 1.35 da Oliforum allenamento EGMO combinatoria
Grazie per la risposta.
Questo mi conferma che il ragionamento che ho fatto, a dire il vero partendo dall'hint, è giusto.
Il mio problema è che non riesco a trovare una sequenza di mosse legali che dalla tabella con $-1$ nella casella centrale mi faccia ottenere una tabella con $+1$ in tutte le caselle.
Questo mi conferma che il ragionamento che ho fatto, a dire il vero partendo dall'hint, è giusto.
Il mio problema è che non riesco a trovare una sequenza di mosse legali che dalla tabella con $-1$ nella casella centrale mi faccia ottenere una tabella con $+1$ in tutte le caselle.
Re: Esercizio 1.35 da Oliforum allenamento EGMO combinatoria
Coloriamo la tabella a scacchiera, diciamo con [tex]a_{11}[/tex] bianca, allora notiamo che ogni trasformazione [tex]2 \times 2[/tex] e [tex]4 \times 4[/tex] lascia invariato il prodotto delle caselle bianche (che è [tex]-1[/tex]), mentre applicare una trasformazione [tex]5 \times 5[/tex] sostanzialmente non fa altro che "capovolgere il problema" (infatti sarebbe sufficiente trasformare la tabella in una tabella di [tex]-1[/tex] e applicare successivamente la trasformazione [tex]5 \times 5[/tex]), quindi per giungere ad una tabella di [tex]1[/tex] dobbiamo partire "necessariamente" con una trasformazione [tex]3 \times 3[/tex].
Prova
Prova
Testo nascosto:
Re: Esercizio 1.35 da Oliforum allenamento EGMO combinatoria
Ok. In effetti possiamo fare così.
Possiamo prima fare una mossa con la sottotabella $ 3 \times 3 $ nell'angolo in alto a sinistra, poi con la sottotabella $ 3 \times 3 $ nell'angolo in basso a destra. Rimarranno così due sottotabelle $ 2 \times 2 $ nell’angolo in alto a destra e nell’angolo in basso a sinistra. Facciamo una mossa con ciascuna di queste due sottotabelle e rimarremo con la tabella $ 5 \times 5 $ con tutte e caselle che contengno $ -1 $. A questo punto possiamo fare una mossa con la tabella $ 5 \times 5 $ ottenere tutti $ +1 $
Grazie
Possiamo prima fare una mossa con la sottotabella $ 3 \times 3 $ nell'angolo in alto a sinistra, poi con la sottotabella $ 3 \times 3 $ nell'angolo in basso a destra. Rimarranno così due sottotabelle $ 2 \times 2 $ nell’angolo in alto a destra e nell’angolo in basso a sinistra. Facciamo una mossa con ciascuna di queste due sottotabelle e rimarremo con la tabella $ 5 \times 5 $ con tutte e caselle che contengno $ -1 $. A questo punto possiamo fare una mossa con la tabella $ 5 \times 5 $ ottenere tutti $ +1 $
Grazie