Esercizio 1.35 da Oliforum allenamento EGMO combinatoria

[Nadal01]

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.

[Gizeta]

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:

Niente, non varia!
Segue che [tex]-1[/tex] non può stare in alcuna delle caselle con [tex]j \not = 3[/tex], in caso contrario sarebbe impossibile ottenere un quadrato di [tex]1[/tex] (in cui, banalmente, si ha [tex]p=1[/tex]).
Ora ripeti il ragionamento considerando il prodotto [tex]q[/tex] dei numeri presenti all'interno di tutte le caselle con [tex]i \not = 3[/tex] e deduci che [tex]-1[/tex] non può stare nemmeno in queste.

Quindi, affinché possa esserci la possibilità di ottenere un quadrato di soli [tex]1[/tex], l'unica casella che può ospitare [tex]-1[/tex] è quella di indici [tex]i=j=3[/tex], ossia [tex]a_{33}[/tex], ossia la casella centrale; ora ti basta trovare una sequenza di mosse legali che ti permetta di ottenere una tabella di soli [tex]1[/tex] nel caso [tex]a_{33}=-1[/tex].

[Nadal01]

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.

[Gizeta]

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

Testo nascosto:

a cominciare applicando una trasformazione [tex]3 \times 3[/tex] al quadrato avente come vertice in altro a sinistra la casella [tex]a_{13}.[/tex]

[Nadal01]

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