We have an \(N\times N\) board of disks. A move chooses one disk and flips every disk in the same row and the same column, with the chosen center disk flipped only once. The initial black disks are exactly those lattice points \((x,y)\) in the first quadrant annulus
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\},$$
with \(0\le x,y\le N-1\). Let \(T(N)\) be the minimum number of moves needed to turn all disks white. The implementation eventually sums
$$\sum_{i=3}^{31} T(2^i-i).$$
1) Write the puzzle as a linear system over \(\mathbb F_2\).
Let \(b_{x,y}\in\{0,1\}\) be the initial color of cell \((x,y)\): \(1\) for black, \(0\) for white. Let \(m_{x,y}\in\{0,1\}\) indicate whether we perform the cross-flip centered at \((x,y)\).
Define the row and column parities of the move pattern:
$$r_x=\sum_{y=0}^{N-1} m_{x,y}\pmod 2,\qquad c_y=\sum_{x=0}^{N-1} m_{x,y}\pmod 2.$$
A cell \((x,y)\) is flipped by every chosen center in row \(x\), by every chosen center in column \(y\), and by the center \((x,y)\) itself. Over \(\mathbb F_2\) this gives
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
So solving the puzzle means finding a \(0/1\) matrix \(m\) satisfying this equation.
2) The only information the code needs from the initial board is the row parity.
For each fixed \(x\), define
$$\rho_x=\sum_{y=0}^{N-1} b_{x,y}\pmod 2.$$
Because the initial black set is the annulus \(\mathcal A_N\), the black cells in row \(x\) form a contiguous interval in \(y\). Its endpoints are
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,$$
$$y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor.$$
If \(y_{\max}\ge y_{\min}\), the number of black cells in that row is
$$c_x=y_{\max}(x)-y_{\min}(x)+1,$$
hence
$$\rho_x\equiv c_x\pmod 2.$$
If the interval is empty, then \(\rho_x=0\). The array rho in the C++ code stores exactly these parities.
3) Even \(N\): summing the linear system across a row determines the row parities of the solution.
Sum
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
over all \(y\). Since \(\sum_y m_{x,y}=r_x\), we obtain
$$\rho_x=r_x+N r_x + C\pmod 2,$$
where
$$C=\sum_{y=0}^{N-1} c_y\pmod 2$$
is the total parity of the move matrix. When \(N\) is even, \(N r_x\equiv 0\), so
$$r_x=\rho_x+C.$$
By symmetry of the annulus, the same argument for columns gives
$$c_y=\rho_y+R,$$
with \(R=\sum_x r_x\). But total row parity equals total column parity, so \(R=C\).
4) For even \(N\), the constant \(C\) is just the parity of the number of odd rows.
Let
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1.$$
Summing \(r_x=\rho_x+C\) over \(x\), and using that \(N\) is even, gives
$$C=\sum_x r_x\equiv \sum_x \rho_x \equiv N_1\pmod 2.$$
So for even \(N\),
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) Therefore each move bit \(m_{x,y}\) can be written directly from the annulus data.
Substitute the row and column formulas into
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2.$$
The two \(N_1\) terms cancel, so for even \(N\)
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
This is the key closed form behind the code.
6) Count the number of ones in the solution matrix.
If a cell is white initially (\(b_{x,y}=0\)), then
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
If a cell is black initially (\(b_{x,y}=1\)), then
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
Across the full \(N\times N\) board, the number of pairs \((x,y)\) with different row/column parity is exactly
$$2N_0N_1.$$
That is the code's base term.
7) Black cells require a signed correction.
The base term \(2N_0N_1\) counts all cells with \(\rho_x\ne \rho_y\) as \(1\). But on black annulus cells the rule is reversed: we want \(1\) when \(\rho_x=\rho_y\), and \(0\) otherwise. So each black cell contributes a correction
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
Hence for even \(N\) the exact formula implemented by the program is
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
This is exactly what compute_adjust evaluates.
8) Odd \(N\) behaves differently.
When \(N\) is odd, summing the row equation gives
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2,$$
because \(N+1\) is even. So in any solvable odd-\(N\) instance, every row parity \(\rho_x\) must be the same. In this annulus family that almost never happens. The current C++ implementation therefore uses the special branch
$$T(5)=3,\qquad T(N)=0\text{ for odd }N\ne 5.$$
The value \(T(5)=3\) is the explicit checkpoint from the problem statement.
9) Concrete checks.
The implementation matches the standard sample values
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
These are strong sanity checks for the annulus-parity formula.
1) For each \(x\in[0,N-1]\), compute the annulus interval \([y_{\min}(x),y_{\max}(x)]\).
2) Store \(\rho_x\), the parity of the number of black cells in that row, and count \(N_1\).
3) If \(N\) is odd, return the code's special-case value.
4) Otherwise start from the base count \(2N_0N_1\).
5) Iterate over all annulus cells and add \(+1\) or \(-1\) according to whether \(\rho_x=\rho_y\).
The row-parity phase touches each \(x\) once, so it is \(O(N)\). The correction phase iterates all lattice points in a quarter-annulus of thickness \(1\), whose size is \(\Theta(N)\). Therefore the whole method is essentially
$$O(N)$$
time with
$$O(N)$$
memory for rho. The implementation parallelizes both passes over chunks of \(x\).
The code explicitly checks
$$T(5)=3,$$
and the same formula gives the known values
$$T(10)=29,\qquad T(1000)=395253.$$
The final program then sums \(T(2^i-i)\) for \(3\le i\le 31\).
Wir haben ein \(N\times N\)-Brett aus Scheiben. Ein Zug waehlt eine Scheibe und kippt alle Scheiben in derselben Zeile und derselben Spalte; die gewaehlte Mittelscheibe wird nur einmal gezaehlt. Anfangs sind genau die Punkte
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}$$
schwarz. Gesucht ist die minimale Zugzahl \(T(N)\). Das Programm summiert schliesslich \(\sum_{i=3}^{31}T(2^i-i)\).
1) Formuliere das Problem ueber \(\mathbb F_2\).
Sei \(b_{x,y}\) die Anfangsfarbe und \(m_{x,y}\) die Entscheidung, ob der Kreuzzug im Feld \((x,y)\) ausgefuehrt wird. Mit den Zeilen- und Spaltenparitaeten
$$r_x=\sum_y m_{x,y},\qquad c_y=\sum_x m_{x,y}\pmod 2$$
gilt fuer jedes Feld
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
2) Aus dem Startbrett braucht der Code nur die Zeilenparitaeten.
Definiere
$$\rho_x=\sum_y b_{x,y}\pmod 2.$$
Da die schwarzen Felder in Zeile \(x\) ein zusammenhaengendes Intervall bilden, sind die Grenzen
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor,$$
und damit
$$\rho_x\equiv y_{\max}(x)-y_{\min}(x)+1\pmod 2$$
wenn das Intervall nicht leer ist.
3) Gerade \(N\): Zeilensummen bestimmen die Loesungsparitaeten.
Summiert man die Gleichung \(m_{x,y}+r_x+c_y=b_{x,y}\) ueber alle \(y\), erhaelt man
$$\rho_x=r_x+Nr_x+C\pmod 2,$$
wobei \(C=\sum_y c_y\). Fuer gerades \(N\) folgt
$$r_x=\rho_x+C.$$
Analog gilt spaltensymmetrisch
$$c_y=\rho_y+R,$$
und wegen Gesamtparitaet ist \(R=C\).
4) Die Konstante ist bei geradem \(N\) gleich der Paritaet der ungeraden Zeilen.
Mit
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1$$
ergibt Summation ueber \(x\):
$$C\equiv N_1\pmod 2.$$
Also
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) Daraus folgt eine direkte Formel fuer die Zugmatrix.
In
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2$$
heben sich die beiden \(N_1\)-Terme weg. Damit gilt bei geradem \(N\)
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
6) Wie zaehlt man nun die Einsen?
Auf weissen Feldern (\(b_{x,y}=0\)) ist \(m_{x,y}=1\) genau dann, wenn \(\rho_x\ne\rho_y\). Auf schwarzen Feldern (\(b_{x,y}=1\)) kehrt sich die Bedingung um: dann braucht man \(m_{x,y}=1\) genau bei \(\rho_x=\rho_y\).
Ueber das gesamte Brett gibt es
$$2N_0N_1$$
Paare \((x,y)\) mit unterschiedlicher Paritaet. Das ist der Basisterm im Code.
7) Schwarze Ringpunkte liefern die Vorzeichenkorrektur.
Fuer jeden schwarzen Punkt \((x,y)\in\mathcal A_N\) muss der Basisterm korrigiert werden um
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne\rho_y. \end{cases}$$
Damit lautet die im Programm benutzte exakte Formel fuer gerades \(N\)
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
8) Ungerade \(N\) sind ein Sonderfall.
Ist \(N\) ungerade, dann liefert die Zeilensumme
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2.$$
Also muessen in jedem loesbaren Fall alle \(\rho_x\) gleich sein. In dieser Ringfamilie passiert das praktisch nie. Deshalb verwendet die aktuelle C++-Implementierung die Sonderbehandlung
$$T(5)=3,\qquad T(N)=0\text{ fuer ungerade }N\ne 5.$$
9) Stichproben.
Die Methode reproduziert die Standardwerte
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1) Berechne fuer jedes \(x\) das Ringintervall \([y_{\min}(x),y_{\max}(x)]\).
2) Speichere \(\rho_x\) und zaehle \(N_1\).
3) Behandle ungerade \(N\) mit dem Sonderpfad des Codes.
4) Starte bei \(2N_0N_1\).
5) Laufe alle Ringpunkte durch und addiere \(+1\) oder \(-1\) je nach Vergleich von \(\rho_x\) und \(\rho_y\).
Die Paritaetsphase ist \(O(N)\). Auch der Ring selbst hat wegen Dicke \(1\) nur \(\Theta(N)\) Gitterpunkte. Insgesamt arbeitet die Methode also im Wesentlichen in
$$O(N)$$
Zeit bei
$$O(N)$$
Speicher.
Geprueft werden
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
Danach summiert das Programm \(T(2^i-i)\) fuer \(3\le i\le 31\).
\(N\times N\) bir disk tahtamiz var. Bir hamle, bir diski merkez secer ve ayni satirdaki ve ayni sutundaki tum diskleri cevirir; secilen merkez disk yalnizca bir kez çevrilmis sayilir. Baslangicta siyah olan diskler tam olarak
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}$$
halka bolgesindeki noktalardir. \(T(N)\), tum diskleri beyaza cevirmek icin gereken minimum hamle sayisidir. Kod sonunda
$$\sum_{i=3}^{31}T(2^i-i)$$
toplamini hesaplar.
1) Problemi \(\mathbb F_2\) uzerinde lineer sisteme cevir.
\(b_{x,y}\) baslangic renginin, \(m_{x,y}\) ise \((x,y)\) merkezli cross-flip hamlesinin secilip secilmediginin \(0/1\) gostergesi olsun. Hamle matrisinin satir ve sutun pariteleri
$$r_x=\sum_y m_{x,y}\pmod 2,\qquad c_y=\sum_x m_{x,y}\pmod 2$$
olarak tanimlanir. Bir hucre \((x,y)\), kendi satirindaki tum secimlerden, kendi sutunundaki tum secimlerden ve kendi merkez seciminden etkilenir. Mod \(2\)'de bu
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
denklemini verir.
2) Kod, baslangic tahtasindan yalnizca satir paritesini cikarir.
Her \(x\) icin
$$\rho_x=\sum_y b_{x,y}\pmod 2$$
olsun. Siyah hucereler halka oldugu icin sabit \(x\)'te siyah \(y\)'ler tek bir aralik olusturur:
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor.$$
Aralik bos degilse siyah hucre sayisi
$$c_x=y_{\max}(x)-y_{\min}(x)+1$$
ve dolayisiyla
$$\rho_x\equiv c_x\pmod 2$$
olur. rho dizisi tam olarak bu bilgiyi saklar.
3) Cift \(N\) icin satir toplamlarini alinca cozum pariteleri belirlenir.
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
denklemini tum \(y\)'ler boyunca toplayalim. \(\sum_y m_{x,y}=r_x\) oldugu icin
$$\rho_x=r_x+Nr_x+C\pmod 2$$
elde edilir; burada
$$C=\sum_y c_y\pmod 2$$
hamle matrisinin toplam paritesidir. \(N\) ciftse \(Nr_x\equiv 0\), dolayisiyla
$$r_x=\rho_x+C.$$
Aynı arguman sutunlar icin
$$c_y=\rho_y+R$$
verir; toplam satir ve toplam sutun paritesi esit oldugundan \(R=C\).
4) Cift \(N\) icin bu sabit, tek pariteli satir sayisinin paritesidir.
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1$$
diyelim. \(r_x=\rho_x+C\) esitligini \(x\) boyunca toplayinca ve \(N\) cift oldugu icin \(NC\) terimi dusunce
$$C\equiv N_1\pmod 2$$
cikar. Bu nedenle
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) Boylece hamle matrisi dogrudan halka verisinden yazilir.
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2$$
ifadesinde iki \(N_1\) terimi birbirini yok eder. Sonuc:
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
Bu, koddaki formülün cekirdeğidir.
6) Simdi 1'lerin sayisini sayalim.
Eger hucre baslangicta beyazsa (\(b_{x,y}=0\)),
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
Eger hucre baslangicta siyahsa (\(b_{x,y}=1\)),
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
Tum tahta uzerinde \(\rho_x\ne \rho_y\) olan ciftlerin sayisi
$$2N_0N_1$$
olur. Kodun baslangic terimi tam olarak budur.
7) Siyah halka noktalarinda isaretli duzeltme gerekir.
Temel terim, farkli pariteli her hucreyi \(1\) sayar. Oysa siyah hucrelerde kural tersine doner: orada \(1\) olmasi icin \(\rho_x=\rho_y\) gerekir. Bu nedenle her siyah halka noktasi icin su duzeltme eklenir:
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
Sonucta cift \(N\) icin kodun hesapladigi exact ifade
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y)$$
olur.
8) Tek \(N\) icin durum farklidir.
\(N\) tekse satir toplami
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2$$
verir; cunku \(N+1\) cifttir. Demek ki cozulur bir tek-\(N\) ornekte tum satir pariteleri ayni olmak zorundadir. Bu halka ailesinde bu kosul neredeyse hic saglanmaz. Mevcut C++ kodu bu nedenle
$$T(5)=3,\qquad T(N)=0\text{ for odd }N\ne 5$$
ozel dalini kullanir.
9) Kucuk kontrol degerleri.
Yontem bilinen ornekleri verir:
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1) Her \(x\) icin halka araligi \([y_{\min}(x),y_{\max}(x)]\) hesapla.
2) \(\rho_x\) paritesini bul ve \(N_1\)'i say.
3) \(N\) tekse kodun ozel-case dondurusunu uygula.
4) Aksi halde \(2N_0N_1\) ile basla.
5) Tum halka noktalarini dolasip \(\rho_x=\rho_y\) ise \(+1\), degilse \(-1\) ekle.
Satir paritesi asamasi \(O(N)\) dir. Kalinligi \(1\) olan ceyrek halkanin kafes nokta sayisi da \(\Theta(N)\) oldugu icin duzeltme gecisi de efektif olarak lineerdir. Dolayisiyla toplam maliyet
$$O(N)$$
zaman ve
$$O(N)$$
bellektir. Kod her iki asamayi da \(x\)-bloklari bazinda paralellestirir.
Kod acikca
$$T(5)=3$$
degerini kontrol eder; ayni formulle
$$T(10)=29,\qquad T(1000)=395253$$
degerleri de elde edilir. Sonra \(3\le i\le 31\) icin \(T(2^i-i)\) toplanir.
Tenemos un tablero \(N\times N\) de discos. Un movimiento elige un disco y cambia todos los discos de su fila y de su columna, contando el disco central solo una vez. Al inicio, los discos negros son exactamente los puntos del anillo
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}.$$
Sea \(T(N)\) el numero minimo de movimientos para volver todo blanco. El programa suma finalmente \(\sum_{i=3}^{31}T(2^i-i)\).
1) El problema se vuelve lineal sobre \(\mathbb F_2\).
Sea \(b_{x,y}\) el color inicial y \(m_{x,y}\) la decision de aplicar o no el cross-flip centrado en \((x,y)\). Definimos
$$r_x=\sum_y m_{x,y}\pmod 2,\qquad c_y=\sum_x m_{x,y}\pmod 2.$$
Entonces cada celda satisface
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
2) Solo importa la paridad de cada fila del tablero inicial.
Definimos
$$\rho_x=\sum_y b_{x,y}\pmod 2.$$
Como las celdas negras de una fila forman un intervalo continuo del anillo, sus extremos son
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor,$$
y si el intervalo no es vacio,
$$\rho_x\equiv y_{\max}(x)-y_{\min}(x)+1\pmod 2.$$
3) Para \(N\) par, las sumas por fila fijan la estructura de la solucion.
Al sumar \(m_{x,y}+r_x+c_y=b_{x,y}\) sobre todos los \(y\), resulta
$$\rho_x=r_x+Nr_x+C\pmod 2,$$
donde \(C=\sum_y c_y\). Si \(N\) es par, entonces
$$r_x=\rho_x+C.$$
Por simetria, tambien
$$c_y=\rho_y+R,$$
y como la paridad total por filas y por columnas coincide, \(R=C\).
4) La constante \(C\) es la paridad del numero de filas impares.
Con
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1,$$
se obtiene
$$C\equiv N_1\pmod 2,$$
y por tanto
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) La matriz de movimientos queda explicitamente determinada.
Al sustituir en
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2$$
se cancelan los dos terminos \(N_1\), y queda
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
6) Conteo de unos.
En una celda blanca (\(b_{x,y}=0\)),
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
En una celda negra (\(b_{x,y}=1\)),
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
Sobre todo el tablero, el numero de pares \((x,y)\) con paridades distintas es
$$2N_0N_1,$$
que es exactamente el termino base del codigo.
7) Las celdas negras aportan una correccion con signo.
Cada punto negro del anillo corrige el conteo base en
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
Por eso, para \(N\) par, la formula implementada es
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
8) El caso impar cambia por completo.
Si \(N\) es impar, al sumar por filas se obtiene
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2.$$
Luego, en cualquier instancia soluble, todas las paridades de fila deben coincidir. En esta familia de anillos eso casi nunca ocurre, y la implementacion C++ usa la rama especial
$$T(5)=3,\qquad T(N)=0\text{ para }N\text{ impar},\ N\ne 5.$$
9) Ejemplos de control.
La formula reproduce
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1) Para cada \(x\), calcular el intervalo \([y_{\min}(x),y_{\max}(x)]\).
2) Obtener \(\rho_x\) y contar \(N_1\).
3) Si \(N\) es impar, usar la salida especial del codigo.
4) Empezar con \(2N_0N_1\).
5) Recorrer los puntos del anillo y sumar \(+1\) o \(-1\) segun \(\rho_x=\rho_y\).
La fase de paridades es \(O(N)\). El anillo de grosor \(1\) en el primer cuadrante tiene \(\Theta(N)\) puntos de red, asi que el ajuste tambien es esencialmente lineal. El coste total es
$$O(N)$$
tiempo y
$$O(N)$$
memoria.
El codigo comprueba
$$T(5)=3,$$
y la misma formula da
$$T(10)=29,\qquad T(1000)=395253.$$
Despues suma \(T(2^i-i)\) para \(3\le i\le 31\).
我们有一个 \(N\times N\) 的圆盘棋盘。一次操作选择一个圆盘，把该圆盘所在行和所在列上的所有圆盘翻转，中心圆盘只翻一次。初始黑盘正好是第一象限环带
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}$$
中的格点。记 \(T(N)\) 为把全盘变白所需的最少操作数。程序最终求和
$$\sum_{i=3}^{31}T(2^i-i).$$
1）把问题写成 \(\mathbb F_2\) 上的线性系统。
设 \(b_{x,y}\in\{0,1\}\) 表示初始颜色，\(m_{x,y}\in\{0,1\}\) 表示是否在 \((x,y)\) 处执行 cross flip。再定义操作矩阵的行奇偶与列奇偶：
$$r_x=\sum_y m_{x,y}\pmod 2,\qquad c_y=\sum_x m_{x,y}\pmod 2.$$
那么每个位置满足
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
2）代码只需要初始棋盘每一行的黑子奇偶。
定义
$$\rho_x=\sum_y b_{x,y}\pmod 2.$$
由于固定 \(x\) 时，环带与该行的交集是一个连续的 \(y\) 区间，所以端点为
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor.$$
若区间非空，则黑子个数为
$$c_x=y_{\max}(x)-y_{\min}(x)+1,$$
从而
$$\rho_x\equiv c_x\pmod 2.$$
3）当 \(N\) 为偶数时，按行求和即可确定解的行奇偶。
把
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
对所有 \(y\) 求和，得到
$$\rho_x=r_x+Nr_x+C\pmod 2,$$
其中
$$C=\sum_y c_y\pmod 2.$$
若 \(N\) 为偶数，则 \(Nr_x\equiv 0\)，所以
$$r_x=\rho_x+C.$$
由对称性，同理有
$$c_y=\rho_y+R,$$
而总行奇偶与总列奇偶相同，因此 \(R=C\)。
4）这个常数就是奇行数的奇偶。
记
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1.$$
把 \(r_x=\rho_x+C\) 再对 \(x\) 求和，且利用 \(N\) 为偶数，可得
$$C\equiv N_1\pmod 2.$$
因此
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5）于是每个操作位 \(m_{x,y}\) 都能直接写出。
代回
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2,$$
两个 \(N_1\) 项相互抵消，于是偶数 \(N\) 时有
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
6）接下来只需统计这个矩阵里有多少个 \(1\)。
若某格初始是白色，即 \(b_{x,y}=0\)，则
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
若某格初始是黑色，即 \(b_{x,y}=1\)，则
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
在整个 \(N\times N\) 棋盘上，\(\rho_x\ne\rho_y\) 的有序对数量正好是
$$2N_0N_1,$$
这就是代码中的基项。
7）黑色环带点需要一个带符号修正。
对每个黑点 \((x,y)\in\mathcal A_N\)，相对基项要增加或减少
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
因此偶数 \(N\) 下，程序实际计算的是
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
8）奇数 \(N\) 的情形完全不同。
若 \(N\) 为奇数，则按行求和得到
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2,$$
因为 \(N+1\) 为偶数。也就是说，若奇数 \(N\) 的实例可解，则所有行奇偶 \(\rho_x\) 必须完全相同。在这个环带家族中，这几乎从不发生。因此当前 C++ 代码采用特殊分支
$$T(5)=3,\qquad T(N)=0\text{ for odd }N\ne 5.$$
9）检查值。
该公式重现了已知样例
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1） 对每个 \(x\) 计算环带交段 \([y_{\min}(x),y_{\max}(x)]\)。
2） 得到 \(\rho_x\) 并统计 \(N_1\)。
3） 若 \(N\) 为奇数，则走代码的特殊返回路径。
4） 否则先取基项 \(2N_0N_1\)。
5） 遍历环带中的所有黑点，根据 \(\rho_x\) 与 \(\rho_y\) 是否相等加上 \(+1\) 或 \(-1\)。
行奇偶计算是 \(O(N)\)。厚度为 \(1\) 的第一象限环带格点数也是 \(\Theta(N)\)，因此修正阶段同样本质上线性。总复杂度为
$$O(N)$$
时间和
$$O(N)$$
空间。
代码显式检查
$$T(5)=3,$$
同一公式还能得到
$$T(10)=29,\qquad T(1000)=395253.$$
随后程序求和 \(T(2^i-i)\)（\(3\le i\le 31\)）。
Есть доска \(N\times N\). Ход выбирает одну фишку и переворачивает всю ее строку и весь ее столбец, причем центральная фишка считается один раз. Изначально черны именно точки кольца
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}.$$
Обозначим через \(T(N)\) минимальное число ходов для получения полностью белой доски. Программа в итоге суммирует \(\sum_{i=3}^{31}T(2^i-i)\).
1) Это линейная система над \(\mathbb F_2\).
Пусть \(b_{x,y}\) - начальный цвет клетки, а \(m_{x,y}\) показывает, делаем ли ход с центром \((x,y)\). Введем паритеты строк и столбцов матрицы ходов:
$$r_x=\sum_y m_{x,y}\pmod 2,\qquad c_y=\sum_x m_{x,y}\pmod 2.$$
Тогда для каждой клетки
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
2) Из исходной конфигурации нужен только паритет каждой строки.
Определим
$$\rho_x=\sum_y b_{x,y}\pmod 2.$$
Так как черные клетки в строке \(x\) образуют непрерывный отрезок кольца, его границы равны
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor,$$
и если отрезок не пуст, то
$$\rho_x\equiv y_{\max}(x)-y_{\min}(x)+1\pmod 2.$$
3) Для четного \(N\) суммы по строкам определяют паритеты решения.
Просуммируем
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
по всем \(y\). Получаем
$$\rho_x=r_x+Nr_x+C\pmod 2,$$
где
$$C=\sum_y c_y\pmod 2.$$
Если \(N\) четно, то \(Nr_x\equiv 0\), поэтому
$$r_x=\rho_x+C.$$
По симметрии столбцов аналогично
$$c_y=\rho_y+R,$$
и из равенства общей паритетности строк и столбцов имеем \(R=C\).
4) Константа \(C\) равна паритету числа нечетных строк.
Если
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1,$$
то суммирование \(r_x=\rho_x+C\) по \(x\) дает
$$C\equiv N_1\pmod 2.$$
Следовательно,
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) Отсюда сразу получается формула для матрицы ходов.
Подставляя в
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2,$$
получаем сокращение двух членов \(N_1\), и при четном \(N\)
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
6) Теперь остается посчитать число единиц.
Если клетка белая (\(b_{x,y}=0\)), то
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
Если клетка черная (\(b_{x,y}=1\)), то
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
На всей доске количество пар \((x,y)\) с \(\rho_x\ne \rho_y\) равно
$$2N_0N_1,$$
и это базовый член программы.
7) Черные точки кольца дают знаковую поправку.
Для каждой черной точки \((x,y)\in\mathcal A_N\) нужно поправить базовый счет на
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
Тем самым для четного \(N\) код вычисляет
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
8) При нечетном \(N\) возникает другое условие разрешимости.
Если \(N\) нечетно, то
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2,$$
поскольку \(N+1\) четно. Значит, во всяком разрешимом случае все \(\rho_x\) должны совпадать. Для данной кольцевой семьи это почти никогда не выполняется, поэтому текущая реализация использует
$$T(5)=3,\qquad T(N)=0\text{ для нечетных }N\ne 5.$$
9) Контрольные значения.
Формула воспроизводит
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1) Для каждого \(x\) найти кольцевой отрезок \([y_{\min}(x),y_{\max}(x)]\).
2) Посчитать \(\rho_x\) и число \(N_1\).
3) При нечетном \(N\) использовать специальную ветку кода.
4) Иначе начать с \(2N_0N_1\).
5) Обойти все точки кольца и прибавлять \(+1\) или \(-1\) по сравнению \(\rho_x\) и \(\rho_y\).
Фаза вычисления паритетов строк занимает \(O(N)\). Число точек в кольце толщины \(1\) также равно \(\Theta(N)\), поэтому вся схема работает фактически за
$$O(N)$$
времени и требует
$$O(N)$$
памяти.
Код явно проверяет
$$T(5)=3,$$
а та же формула дает
$$T(10)=29,\qquad T(1000)=395253.$$
После этого программа суммирует \(T(2^i-i)\) для \(3\le i\le 31\).
لدينا لوح \(N\times N\) من الأقراص. في كل حركة نختار قرصًا ونقلب كل الأقراص في صفه وعموده، مع احتساب القرص المركزي مرة واحدة فقط. الأقراص السوداء في البداية هي تمامًا نقاط الحلقة
$$\mathcal A_N=\{(x,y)\in\mathbb Z_{\ge 0}^2:(N-1)^2\le x^2+y^2<N^2\}.$$
ولتكن \(T(N)\) أقل عدد من الحركات اللازمة لجعل اللوح كله أبيض. البرنامج يجمع في النهاية
$$\sum_{i=3}^{31}T(2^i-i).$$
1) المسألة تتحول إلى نظام خطي فوق \(\mathbb F_2\).
لنرمز إلى اللون الابتدائي بالمتغير \(b_{x,y}\in\{0,1\}\)، وإلى اختيار الحركة ذات المركز \((x,y)\) بالمتغير \(m_{x,y}\in\{0,1\}\). ونعرّف زوجية صفوف وأعمدة مصفوفة الحركات:
$$r_x=\sum_y m_{x,y}\pmod 2,\qquad c_y=\sum_x m_{x,y}\pmod 2.$$
عندئذ تحقق كل خلية العلاقة
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2.$$
2) من اللوح الابتدائي نحتاج فقط زوجية كل صف.
نعرّف
$$\rho_x=\sum_y b_{x,y}\pmod 2.$$
وبما أن الخلايا السوداء في الصف \(x\) تشكل فترة متصلة داخل الحلقة، فإن طرفيها هما
$$y_{\min}(x)=\left\lceil\sqrt{(N-1)^2-x^2}\right\rceil,\qquad y_{\max}(x)=\left\lfloor\sqrt{N^2-x^2-1}\right\rfloor.$$
وإذا لم تكن الفترة فارغة، فعدد الخلايا السوداء فيها هو
$$c_x=y_{\max}(x)-y_{\min}(x)+1,$$
ومن ثم
$$\rho_x\equiv c_x\pmod 2.$$
3) عندما يكون \(N\) زوجيًا فإن جمع المعادلات على الصف يحدد بنية الحل.
بجمع
$$m_{x,y}+r_x+c_y=b_{x,y}\pmod 2$$
على جميع قيم \(y\) نحصل على
$$\rho_x=r_x+Nr_x+C\pmod 2,$$
حيث
$$C=\sum_y c_y\pmod 2.$$
وبما أن \(N\) زوجي، فإن \(Nr_x\equiv 0\)، ولذلك
$$r_x=\rho_x+C.$$
وبالطريقة نفسها على الأعمدة نحصل على
$$c_y=\rho_y+R,$$
ومع تساوي زوجية المجموع الكلي للصفوف والأعمدة يكون \(R=C\).
4) هذه الثابتة هي زوجية عدد الصفوف ذات الزوجية \(1\).
إذا كتبنا
$$N_1=\#\{x:\rho_x=1\},\qquad N_0=N-N_1,$$
فإن جمع العلاقة \(r_x=\rho_x+C\) على جميع \(x\) يعطي
$$C\equiv N_1\pmod 2.$$
وهكذا نحصل على
$$r_x=\rho_x+N_1,\qquad c_y=\rho_y+N_1\pmod 2.$$
5) عند هذه النقطة تصبح مصفوفة الحركات صريحة.
بالتعويض في
$$m_{x,y}=b_{x,y}+r_x+c_y\pmod 2$$
يلغى حدّا \(N_1\)، فنحصل في حالة \(N\) الزوجي على
$$m_{x,y}=b_{x,y}+\rho_x+\rho_y\pmod 2.$$
6) الآن نعد عدد الواحدات في مصفوفة الحركات.
إذا كانت الخلية بيضاء في البداية (\(b_{x,y}=0\))، فإن
$$m_{x,y}=1\iff \rho_x\ne \rho_y.$$
أما إذا كانت سوداء في البداية (\(b_{x,y}=1\))، فإن
$$m_{x,y}=1\iff \rho_x=\rho_y.$$
وعلى اللوح كله فإن عدد الأزواج \((x,y)\) التي تحقق \(\rho_x\ne\rho_y\) يساوي
$$2N_0N_1,$$
وهذا هو الحد الأساسي في الكود.
7) نقاط الحلقة السوداء تضيف تصحيحًا بإشارة.
لكل نقطة سوداء \((x,y)\in\mathcal A_N\) نضيف التصحيح
$$\operatorname{sgn}(x,y)= \begin{cases} +1,&\rho_x=\rho_y,\\ -1,&\rho_x\ne \rho_y. \end{cases}$$
ولذلك فإن الصيغة التي يطبقها البرنامج في حالة \(N\) الزوجي هي
$$T(N)=2N_0N_1+\sum_{(x,y)\in\mathcal A_N}\operatorname{sgn}(x,y).$$
8) عندما يكون \(N\) فرديًا تظهر حالة قابلية حل مختلفة.
إذا كان \(N\) فرديًا، فإن جمع المعادلات على الصف يعطي
$$\rho_x=(N+1)r_x+C\equiv C\pmod 2,$$
لأن \(N+1\) زوجي. إذن في أي حالة قابلة للحل يجب أن تكون كل قيم \(\rho_x\) متساوية. في عائلة الحلقات هذه لا يحدث ذلك إلا نادرًا جدًا، ولذلك تستخدم نسخة C++ الحالية الفرع الخاص
$$T(5)=3,\qquad T(N)=0\text{ لكل }N\text{ فردي وغير }5.$$
9) قيم تحقق معروفة.
تعيد الصيغة القيم
$$T(5)=3,\qquad T(10)=29,\qquad T(1000)=395253.$$
1) لكل \(x\) نحسب فترة الحلقة \([y_{\min}(x),y_{\max}(x)]\).
2) نحسب \(\rho_x\) ونعد \(N_1\).
3) إذا كان \(N\) فرديًا نستخدم الفرع الخاص الموجود في الكود.
4) وإلا نبدأ من الحد \(2N_0N_1\).
5) نمر على جميع نقاط الحلقة ونضيف \(+1\) أو \(-1\) بحسب تساوي \(\rho_x\) و\(\rho_y\).
مرحلة حساب زوجية الصفوف هي \(O(N)\). وعدد نقاط الحلقة ذات السمك \(1\) في الربع الأول هو أيضًا \(\Theta(N)\)، لذلك تكون الطريقة كلها في الجوهر
$$O(N)$$
زمنًا و
$$O(N)$$
ذاكرة.
يتحقق البرنامج صراحة من
$$T(5)=3,$$
وتعطي الصيغة نفسها
$$T(10)=29,\qquad T(1000)=395253.$$
ثم يجمع بعد ذلك \(T(2^i-i)\) من \(i=3\) إلى \(31\).