We start with a row of 50 grey unit squares. In one tiling we are allowed to use tiles of exactly one non-grey color: red tiles have length 2, green tiles have length 3, and blue tiles have length 4. Grey squares may remain anywhere, colored tiles may touch each other, colors may not be mixed, and the all-grey row is excluded. If \(B_m(n)\) denotes the number of valid tilings of a row of length \(n\) using grey unit squares and tiles of one fixed length \(m\), with at least one colored tile, then the required quantity is
$$B_2(50)+B_3(50)+B_4(50).$$
The three colors do not interact, so the problem is really three separate counting problems that are added at the end.
Fix a tile length \(m\in\{2,3,4\}\), and let \(A_m(n)\) be the number of tilings of a row of length \(n\) when grey squares of length 1 and colored tiles of length \(m\) are both allowed, including the all-grey tiling. Then \(B_m(n)=A_m(n)-1\). The mathematics comes from counting \(A_m(n)\) in two equivalent ways: directly by the number of colored tiles, and recursively by looking at the end of the row.
Once \(m\) is fixed, every legal tiling is made from two kinds of pieces only:
$$\text{grey square of length }1,\qquad \text{colored tile of length }m.$$
There is no mandatory separator between colored tiles, so two red tiles may sit next to each other, two green tiles may sit next to each other, and so on. That is exactly why the recurrence for this problem is simpler than in the separator-based tiling problems: adjacency is allowed, so the only constraint is total length.
Suppose a tiling uses exactly \(k\) colored tiles of length \(m\). Those tiles occupy \(mk\) cells, leaving \(n-mk\) grey squares. Since tiles of the same color are indistinguishable, the question is only how these objects are interleaved along the row.
A convenient compression argument is to shrink each colored tile from length \(m\) to length 1. This removes \(m-1\) cells per colored tile, so the compressed row has length
$$n-(m-1)k.$$
Inside that compressed row we must choose which \(k\) positions are occupied by the colored objects; the remaining positions are grey squares. Therefore the number of tilings with exactly \(k\) colored tiles is
$$\binom{n-(m-1)k}{k}.$$
This formula is valid whenever \(0\le k\le \lfloor n/m\rfloor\).
Adding over every possible value of \(k\) gives the total count including the all-grey row:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Since the problem demands at least one colored tile, we remove the \(k=0\) term:
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
So the whole problem can already be written as
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$$
The code evaluates the same quantity with a small dynamic program. For a row of length \(n\), inspect the last position. Either that last cell is grey, in which case the first \(n-1\) cells form any tiling counted by \(A_m(n-1)\), or the row ends with one colored tile of length \(m\), in which case the first \(n-m\) cells form any tiling counted by \(A_m(n-m)\).
This gives the recurrence
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
together with the initial conditions
$$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0.$$
Equivalently, for \(0\le n<m\) we simply have \(A_m(n)=1\), because the all-grey tiling is the only possibility. For \(m=2\) this is the shifted Fibonacci recurrence \(A_2(n)=F_{n+1}\), while \(m=3\) and \(m=4\) follow the same dynamic idea without needing a special closed form.
The short example in the statement is a perfect check on the formulas.
For red tiles \((m=2)\),
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
The first term counts the 4 placements of one red tile, and the second term counts the 3 placements of two red tiles.
For green tiles \((m=3)\),
$$B_3(5)=\binom{3}{1}=3.$$
For blue tiles \((m=4)\),
$$B_4(5)=\binom{2}{1}=2.$$
Hence the total for length 5 is
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
which matches the known checkpoint and confirms that the three colors are counted separately and then added.
Define
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
Then Problem 116 asks for \(T(50)\). The implementations compute \(A_2(50)\), \(A_3(50)\), and \(A_4(50)\) by recurrence, subtract 1 from each to exclude the all-grey row, and sum the three results.
The C++, Python, and Java implementations all use the same per-color dynamic program. For a chosen tile length \(m\), they allocate a table for row lengths \(0,1,\dots,50\), set the length-0 count to 1, and then fill the table from left to right. At each length \(n\), they begin with the contribution from ending in a grey square, namely the count for \(n-1\), and if \(n\ge m\) they add the contribution from ending in one colored tile of length \(m\).
After the table entry for length 50 has been computed, the implementation subtracts 1 to discard the all-grey tiling. The outer logic repeats the same calculation for \(m=2\), \(m=3\), and \(m=4\), then adds the three one-color answers.
The C++ implementation also includes a small checkpoint based on the length-5 example, while the Python and Java versions directly evaluate the length-50 case. In every language, however, the underlying algorithm is the same recurrence \(A_m(n)=A_m(n-1)+A_m(n-m)\).
For one tile length \(m\), the dynamic program fills one table of size \(n+1\), so it runs in \(O(n)\) time and uses \(O(n)\) memory. Here \(n=50\), so each pass is tiny.
Problem 116 performs exactly three such passes, one for each tile length in \(\{2,3,4\}\). Therefore the total running time is \(O(3n)=O(n)\) and the space usage is \(O(n)\). Because the set of colors is fixed, the constant factor is small; in fact, for \(n=50\) the computation is effectively instantaneous.
Wir beginnen mit einer Reihe aus 50 grauen Einheitsquadraten. In einer einzelnen Belegung darf genau eine nicht-graue Kachelfarbe verwendet werden: rote Steine haben Länge 2, grüne Länge 3 und blaue Länge 4. Graue Felder dürfen an beliebigen Stellen verbleiben, farbige Steine dürfen direkt aneinanderliegen, Farben dürfen nicht gemischt werden, und die vollständig graue Reihe zählt nicht mit. Bezeichne \(B_m(n)\) als die Zahl der gültigen Belegungen einer Reihe der Länge \(n\) mit grauen Einheitsfeldern und farbigen Steinen einer festen Länge \(m\), wobei mindestens ein farbiger Stein benutzt wird. Gesucht ist dann
$$B_2(50)+B_3(50)+B_4(50).$$
Die drei Farben beeinflussen sich also nicht gegenseitig; das Problem zerfällt in drei unabhängige Zählaufgaben, deren Ergebnisse am Ende addiert werden.
Fixiere eine Steinlänge \(m\in\{2,3,4\}\) und bezeichne mit \(A_m(n)\) die Anzahl aller Belegungen einer Reihe der Länge \(n\), wenn graue Felder der Länge 1 und farbige Steine der Länge \(m\) erlaubt sind, einschließlich der vollständig grauen Belegung. Dann gilt \(B_m(n)=A_m(n)-1\). Die zentrale Idee ist, \(A_m(n)\) auf zwei äquivalente Arten zu beschreiben: einmal durch die genaue Zahl farbiger Steine und einmal rekursiv über das Ende der Reihe.
Sobald \(m\) feststeht, gibt es nur noch zwei Bausteintypen:
$$\text{graues Feld der Länge }1,\qquad \text{farbiger Stein der Länge }m.$$
Zwischen zwei farbigen Steinen ist kein Trennfeld vorgeschrieben. Zwei rote, zwei grüne oder zwei blaue Steine dürfen also direkt nebeneinanderliegen. Genau deshalb ist die Rekursion hier einfacher als bei den Aufgaben mit erzwungenen Lücken: Die einzige echte Nebenbedingung ist die Gesamtlänge der Reihe.
Angenommen, eine Belegung benutzt genau \(k\) farbige Steine der Länge \(m\). Diese Steine belegen zusammen \(mk\) Zellen, also bleiben \(n-mk\) graue Einheitsfelder übrig. Da gleichfarbige Steine untereinander nicht unterschieden werden, zählt nur noch, in welcher Reihenfolge die beiden Objekttypen entlang der Reihe auftauchen.
Am bequemsten ist ein Kompressionsargument: Jeder farbige Stein wird von Länge \(m\) auf Länge 1 zusammengeschoben. Dadurch verschwinden pro Farbstein \(m-1\) Zellen, also hat die komprimierte Reihe Länge
$$n-(m-1)k.$$
In dieser komprimierten Reihe müssen wir nur auswählen, welche \(k\) Positionen von farbigen Objekten besetzt werden; alle übrigen Positionen sind grau. Daher ist die Zahl der Belegungen mit genau \(k\) Farbsteinen
$$\binom{n-(m-1)k}{k}.$$
Diese Formel ist genau dann sinnvoll, wenn \(0\le k\le \lfloor n/m\rfloor\).
Summiert man über alle möglichen Werte von \(k\), erhält man die Gesamtzahl einschließlich der vollständig grauen Reihe:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Da in der Aufgabenstellung mindestens ein farbiger Stein verlangt wird, entfernen wir den Term \(k=0\):
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Damit lässt sich die Gesamtantwort bereits als
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}$$
schreiben.
Im Code wird dieselbe Zählung mit dynamischer Programmierung ausgewertet. Betrachte eine Reihe der Länge \(n\) und untersuche ihr letztes Feld. Entweder ist dieses Feld grau; dann werden die ersten \(n-1\) Positionen durch \(A_m(n-1)\) beschrieben. Oder die Reihe endet mit genau einem farbigen Stein der Länge \(m\); dann müssen die ersten \(n-m\) Positionen in \(A_m(n-m)\) gezählt werden.
Daraus folgt die Rekursion
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
zusammen mit den Anfangswerten
$$A_m(0)=1,\qquad A_m(r)=0\text{ für }r<0.$$
Äquivalent dazu gilt für \(0\le n<m\) einfach \(A_m(n)=1\), weil dort nur die vollständig graue Belegung möglich ist. Für \(m=2\) erhält man die verschobene Fibonacci-Folge \(A_2(n)=F_{n+1}\); für \(m=3\) und \(m=4\) bleibt das Prinzip dieselbe lineare Rekursion.
Das Beispiel aus der Aufgabenstellung ist ein idealer Test für die Formeln.
Für rote Steine \((m=2)\) gilt
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
Der erste Term zählt die 4 Platzierungen eines einzelnen roten Steins, der zweite Term die 3 Platzierungen von zwei roten Steinen.
Für grüne Steine \((m=3)\) ist
$$B_3(5)=\binom{3}{1}=3.$$
Für blaue Steine \((m=4)\) ist
$$B_4(5)=\binom{2}{1}=2.$$
Somit ergibt sich insgesamt
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
genau wie im bekannten Kontrollbeispiel. Man sieht daran unmittelbar, dass jede Farbe separat gezählt und erst danach addiert wird.
Definiere
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
Gesucht ist dann \(T(50)\). Die Implementierungen berechnen \(A_2(50)\), \(A_3(50)\) und \(A_4(50)\) mit der Rekursion, ziehen jeweils 1 für die vollständig graue Reihe ab und addieren die drei Einzelfälle.
Die Implementierungen in C++, Python und Java verwenden alle dieselbe dynamische Zählung pro Farbe. Für eine gewählte Steinlänge \(m\) wird eine Tabelle für die Reihenlängen \(0,1,\dots,50\) angelegt, der Wert für Länge 0 auf 1 gesetzt und die Tabelle dann von links nach rechts gefüllt. Für jede Länge \(n\) beginnt man mit dem Beitrag, bei dem das letzte Feld grau ist, also dem Wert für \(n-1\); falls \(n\ge m\) gilt, kommt zusätzlich der Beitrag hinzu, bei dem die Reihe mit einem Farbstein der Länge \(m\) endet.
Sobald der Tabellenwert für Länge 50 feststeht, wird 1 abgezogen, um die vollständig graue Belegung zu entfernen. Danach wird dieselbe Rechnung für \(m=2\), \(m=3\) und \(m=4\) wiederholt, und die drei Ergebnisse werden summiert.
Die C++-Variante enthält zusätzlich einen kleinen Kontrolltest mit der Reihenlänge 5, während Python und Java direkt den Fall \(n=50\) auswerten. In allen drei Sprachen ist der mathematische Kern jedoch identisch: die Rekursion \(A_m(n)=A_m(n-1)+A_m(n-m)\).
Für eine feste Steinlänge \(m\) füllt die dynamische Programmierung genau eine Tabelle der Größe \(n+1\). Damit beträgt die Laufzeit \(O(n)\), und der Speicherverbrauch liegt bei \(O(n)\). Hier ist \(n=50\), also ist jeder einzelne Durchlauf sehr klein.
Problem 116 führt genau drei solche Durchläufe aus, nämlich für die Längen 2, 3 und 4. Insgesamt erhält man also \(O(3n)=O(n)\) Laufzeit und \(O(n)\) Speicher. Weil die Anzahl der Farben fest ist, bleibt der konstante Faktor sehr klein; für \(n=50\) ist die Berechnung praktisch sofort abgeschlossen.
Başlangıçta 50 birim uzunluğunda gri karelerden oluşan bir sıra vardır. Tek bir döşemede yalnızca bir renk türü kullanılabilir: kırmızı taşların uzunluğu 2, yeşillerin 3, mavilerin 4'tür. Gri kareler istenen yerlerde kalabilir, renkli taşlar bitişik durabilir, renkler karıştırılamaz ve tamamen gri sıra sayılmaz. Sabit bir \(m\) için, birim gri kareler ile uzunluğu \(m\) olan tek renk taşları kullanarak uzunluğu \(n\) olan bir sıranın en az bir renkli taş içeren döşeme sayısını \(B_m(n)\) ile gösterelim. Sorulan büyüklük
$$B_2(50)+B_3(50)+B_4(50)$$
ifadesidir. Yani problem, sonunda toplanan üç bağımsız tek-renk sayımına ayrılır.
\(m\in\{2,3,4\}\) sabit olsun. Uzunluğu \(n\) olan bir sıranın, birim gri kareler ve uzunluğu \(m\) olan renkli taşlar kullanılarak elde edilen tüm döşemelerinin sayısını \(A_m(n)\) ile gösterelim; burada tamamen gri döşeme de dahildir. O zaman \(B_m(n)=A_m(n)-1\) olur. Çözüm, \(A_m(n)\) değerini iki eşdeğer biçimde ifade eder: tam olarak kaç renkli taş kullanıldığına göre doğrudan saymak ve sıranın sonuna bakarak bir yineleme kurmak.
\(m\) sabitlendiğinde artık yalnızca iki tür parça vardır:
$$\text{uzunluğu }1\text{ olan gri kare},\qquad \text{uzunluğu }m\text{ olan renkli taş}.$$
Renkli taşlar arasında zorunlu bir ayırıcı yoktur. İki kırmızı taş, iki yeşil taş veya iki mavi taş yan yana gelebilir. Bu ayrıntı önemlidir; çünkü bu problemdeki yineleme, araya gri boşluk zorunluluğu olan döşeme problemlerinden daha basittir. Tek gerçek kısıt toplam uzunluktur.
Bir döşemede tam olarak \(k\) tane, uzunluğu \(m\) olan renkli taş kullanılsın. Bu taşlar toplam \(mk\) hücre kaplar, geriye \(n-mk\) adet gri kare kalır. Aynı renkteki taşlar birbirinden ayırt edilmediği için, aslında saydığımız şey bu iki nesne türünün satır boyunca hangi sırayla dizildiğidir.
Bunu görmek için kullanışlı bir sıkıştırma fikri vardır: Her renkli taşı uzunluğu \(m\) yerine 1 olan tek bir nesneye indirgeriz. Böylece her renkli taş başına \(m-1\) hücre kaybolur ve sıkıştırılmış sıranın uzunluğu
$$n-(m-1)k$$
olur. Bu sıkıştırılmış sırada yalnızca \(k\) konumun renkli nesnelere ait olacağını seçmemiz gerekir; kalan konumlar gri karelerdir. Dolayısıyla tam olarak \(k\) renkli taş içeren döşeme sayısı
$$\binom{n-(m-1)k}{k}$$
olur. Bu formül \(0\le k\le \lfloor n/m\rfloor\) için geçerlidir.
Tüm mümkün \(k\) değerlerini toplarsak, tamamen gri sıra dahil toplam sayıyı elde ederiz:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Soru en az bir renkli taş istediği için \(k=0\) terimini çıkarmamız gerekir:
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Böylece tüm problem doğrudan
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}$$
şeklinde yazılabilir.
Kod aynı niceliği küçük bir dinamik programla hesaplar. Uzunluğu \(n\) olan bir sıranın son hücresine bakılır. Bu son hücre gri ise geriye \(A_m(n-1)\) ile sayılan bir uzunluk-\(n-1\) döşemesi kalır. Sıra sonu uzunluğu \(m\) olan tek bir renkli taşla bitiyorsa, baştaki \(n-m\) hücre \(A_m(n-m)\) ile sayılır.
Böylece
$$A_m(n)=A_m(n-1)+A_m(n-m)$$
yinelemesi ortaya çıkar; başlangıç koşulları da
$$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0$$
şeklindedir. Eşdeğer olarak \(0\le n<m\) için yalnızca tamamen gri döşeme mümkün olduğundan \(A_m(n)=1\) olur. \(m=2\) durumunda bu, kaydırılmış Fibonacci bağıntısı \(A_2(n)=F_{n+1}\) olur; \(m=3\) ve \(m=4\) için de aynı doğrusal yineleme mantığı geçerlidir.
Soruda verilen kısa örnek formüller için ideal bir kontroldür.
Kırmızı taşlar \((m=2)\) için
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
İlk terim tek bir kırmızı taşın 4 yerleşimini, ikinci terim ise iki kırmızı taşın 3 yerleşimini sayar.
Yeşil taşlar \((m=3)\) için
$$B_3(5)=\binom{3}{1}=3.$$
Mavi taşlar \((m=4)\) için
$$B_4(5)=\binom{2}{1}=2.$$
Dolayısıyla toplam
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12$$
olur. Bu, bilinen kontrol değeriyle aynıdır ve her rengin bağımsız sayılıp sonunda toplandığını net biçimde gösterir.
$$T(n)=B_2(n)+B_3(n)+B_4(n)$$
tanımını yapalım. O halde Problem 116'nın istediği şey \(T(50)\)'dir. Uygulamalar \(A_2(50)\), \(A_3(50)\) ve \(A_4(50)\) değerlerini yineleme ile hesaplar, her birinden tamamen gri sırayı çıkarmak için 1 eksiltir ve sonuçları toplar.
C++, Python ve Java uygulamalarının üçü de renk başına aynı dinamik programı kullanır. Seçilen taş uzunluğu \(m\) için \(0,1,\dots,50\) satır uzunluklarını kapsayan bir tablo oluşturulur, uzunluk 0 değeri 1 yapılır ve tablo soldan sağa doldurulur. Her \(n\) için önce son hücrenin gri olduğu durumdan gelen \(n-1\) katkısı alınır; eğer \(n\ge m\) ise sona bir uzunluk-\(m\) renkli taş koyma katkısı da eklenir.
Uzunluk 50 için tablo değeri bulunduğunda, tamamen gri döşemeyi atmak için 1 çıkarılır. Aynı işlem \(m=2\), \(m=3\) ve \(m=4\) için tekrarlanır; sonra üç tek-renk sonucu toplanır.
C++ sürümü, uzunluğu 5 olan örneğe dayalı küçük bir kontrol de içerir; Python ve Java sürümleri doğrudan uzunluk 50 durumunu hesaplar. Ancak bütün dillerde aynı matematik uygulanır: \(A_m(n)=A_m(n-1)+A_m(n-m)\).
Sabit bir \(m\) için dinamik program uzunluğu \(n+1\) olan tek bir tablo doldurur. Bu yüzden çalışma süresi \(O(n)\), bellek kullanımı da \(O(n)\)'dir. Burada \(n=50\) olduğundan her geçiş çok küçüktür.
Problem 116 tam olarak üç böyle geçiş yapar; bunlar 2, 3 ve 4 uzunluklu taşlar içindir. Dolayısıyla toplam süre \(O(3n)=O(n)\), toplam bellek \(O(n)\) olur. Renk sayısı sabit olduğu için sabit katsayı küçüktür; \(n=50\) için hesaplama pratikte anlıktır.
Partimos de una fila de 50 cuadros grises de longitud 1. En una misma configuración solo se permite un color no gris: las fichas rojas miden 2, las verdes 3 y las azules 4. Los cuadros grises pueden quedar en cualquier posición, las fichas coloreadas pueden tocarse, los colores no se mezclan y la fila completamente gris no cuenta. Si \(B_m(n)\) denota el número de recubrimientos válidos de una fila de longitud \(n\) usando cuadros grises unitarios y fichas de una longitud fija \(m\), con al menos una ficha coloreada, entonces la cantidad pedida es
$$B_2(50)+B_3(50)+B_4(50).$$
Por tanto, el problema se descompone en tres conteos independientes, uno por cada longitud de ficha, y solo al final se suman.
Fijemos una longitud \(m\in\{2,3,4\}\). Sea \(A_m(n)\) el número total de recubrimientos de una fila de longitud \(n\) cuando se permiten cuadros grises de longitud 1 y fichas coloreadas de longitud \(m\), incluyendo la fila totalmente gris. Entonces \(B_m(n)=A_m(n)-1\). La idea central es describir \(A_m(n)\) de dos maneras equivalentes: contando cuántas fichas coloreadas aparecen y, por otro lado, construyendo una recurrencia a partir del extremo de la fila.
Una vez fijado \(m\), solo quedan dos tipos de piezas:
$$\text{cuadro gris de longitud }1,\qquad \text{ficha coloreada de longitud }m.$$
No hace falta dejar separaciones obligatorias entre fichas coloreadas. Dos rojas, dos verdes o dos azules pueden ir pegadas. Ese detalle es exactamente lo que simplifica esta pregunta frente a otros problemas de embaldosado con huecos forzados: la única restricción real es que la longitud total siga siendo \(n\).
Supongamos que un recubrimiento utiliza exactamente \(k\) fichas coloreadas de longitud \(m\). Esas fichas ocupan \(mk\) celdas y dejan \(n-mk\) cuadros grises. Como las fichas del mismo color son indistinguibles, el problema consiste solo en decidir cómo se intercalan ambos tipos de objetos a lo largo de la fila.
La forma más limpia de contarlo es comprimir cada ficha coloreada de longitud \(m\) hasta longitud 1. Al hacer eso desaparecen \(m-1\) celdas por ficha, de modo que la fila comprimida tiene longitud
$$n-(m-1)k.$$
En esa fila comprimida debemos elegir qué \(k\) posiciones corresponden a fichas coloreadas; las demás posiciones serán cuadros grises. Por lo tanto, el número de recubrimientos con exactamente \(k\) fichas coloreadas es
$$\binom{n-(m-1)k}{k}.$$
Esto solo tiene sentido cuando \(0\le k\le \lfloor n/m\rfloor\).
Al sumar sobre todos los números admisibles de fichas coloreadas obtenemos el total incluyendo la fila completamente gris:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Como el enunciado exige al menos una ficha coloreada, quitamos el término \(k=0\):
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Así, la respuesta completa también puede escribirse como
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$$
El código calcula la misma cantidad mediante programación dinámica. Para una fila de longitud \(n\), observamos la última posición. O bien esa última celda es gris, en cuyo caso los primeros \(n-1\) lugares forman cualquier configuración contada por \(A_m(n-1)\), o bien la fila termina con una ficha coloreada de longitud \(m\), y entonces los primeros \(n-m\) lugares forman cualquier configuración contada por \(A_m(n-m)\).
Eso produce la recurrencia
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
con condiciones iniciales
$$A_m(0)=1,\qquad A_m(r)=0\text{ para }r<0.$$
De forma equivalente, para \(0\le n<m\) se cumple simplemente \(A_m(n)=1\), porque la única posibilidad es la fila completamente gris. Cuando \(m=2\), la sucesión coincide con la Fibonacci desplazada \(A_2(n)=F_{n+1}\); para \(m=3\) y \(m=4\) el mismo esquema dinámico sigue siendo la forma más transparente de evaluar la cuenta.
El ejemplo corto del enunciado sirve como verificación concreta.
Para fichas rojas \((m=2)\),
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
El primer término cuenta las 4 colocaciones de una sola ficha roja y el segundo las 3 colocaciones de dos fichas rojas.
Para fichas verdes \((m=3)\),
$$B_3(5)=\binom{3}{1}=3.$$
Para fichas azules \((m=4)\),
$$B_4(5)=\binom{2}{1}=2.$$
Por tanto, el total es
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
que coincide con el valor de comprobación conocido y muestra que los tres colores se cuentan por separado.
Definamos
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
Entonces el problema pide \(T(50)\). Las implementaciones calculan \(A_2(50)\), \(A_3(50)\) y \(A_4(50)\) con la recurrencia, restan 1 en cada caso para eliminar la fila totalmente gris y suman los tres resultados.
Las implementaciones en C++, Python y Java siguen exactamente el mismo programa dinámico para cada color. Para una longitud fija \(m\), crean una tabla para las longitudes \(0,1,\dots,50\), inicializan el valor de longitud 0 con 1 y luego rellenan la tabla en orden creciente. En cada longitud \(n\), primero toman la contribución correspondiente a terminar con un cuadro gris, es decir, el valor para \(n-1\); después, si \(n\ge m\), añaden la contribución correspondiente a terminar con una ficha coloreada de longitud \(m\).
Una vez calculada la entrada de longitud 50, la implementación resta 1 para excluir la configuración totalmente gris. El proceso se repite para \(m=2\), \(m=3\) y \(m=4\), y finalmente se suman las tres cuentas de un solo color.
La versión en C++ añade además una pequeña comprobación basada en el ejemplo de longitud 5, mientras que las versiones en Python y Java evalúan directamente el caso de longitud 50. Pero en todos los lenguajes la matemática es la misma: la recurrencia \(A_m(n)=A_m(n-1)+A_m(n-m)\).
Para una longitud fija \(m\), la programación dinámica llena una sola tabla de tamaño \(n+1\). Por ello, el tiempo es \(O(n)\) y la memoria también es \(O(n)\). En este problema \(n=50\), así que cada pasada es muy pequeña.
Problem 116 hace exactamente tres pasadas de ese tipo, una para cada longitud en \(\{2,3,4\}\). En consecuencia, el tiempo total es \(O(3n)=O(n)\) y el uso de memoria sigue siendo \(O(n)\). Como el conjunto de colores es fijo, el factor constante es mínimo; para \(n=50\), el cálculo es esencialmente instantáneo.
题目从一排长度为 50 的灰色单位方格开始。在一次铺法中，只能选择一种非灰色砖块：红砖长度为 2，绿砖长度为 3，蓝砖长度为 4。灰色方格可以保留在任意位置，彩色砖块之间允许紧挨着出现，不同颜色不能混用，而且全灰铺法不计入答案。若 \(B_m(n)\) 表示用单位灰格和长度固定为 \(m\) 的单色砖块铺满长度为 \(n\) 的一行、且至少使用一块彩色砖的方案数，那么题目要求的是
$$B_2(50)+B_3(50)+B_4(50).$$
因此，这道题本质上不是一个“混色”问题，而是三个互不干扰的单色计数问题，最后再把结果相加。
固定一个砖长 \(m\in\{2,3,4\}\)。记 \(A_m(n)\) 为长度为 \(n\) 的一行在允许使用长度 1 的灰格和长度 \(m\) 的单色砖时的总铺法数，其中包括全灰铺法。于是有 \(B_m(n)=A_m(n)-1\)。下面从两个角度描述同一个对象 \(A_m(n)\)：一是按彩色砖块的块数来直接计数，二是用行末的局部结构建立递推。
一旦 \(m\) 固定，合法铺法里就只有两种部件：
$$\text{长度为 }1\text{ 的灰格},\qquad \text{长度为 }m\text{ 的彩色砖。}$$
这里没有“彩色砖之间必须隔开至少一个灰格”的限制。两块红砖、两块绿砖或两块蓝砖都可以直接相邻。正因为没有额外分隔条件，这道题的数学结构比带间隔要求的铺砖题更简单，真正需要满足的只有总长度等于 \(n\)。
设某个铺法恰好使用了 \(k\) 块长度为 \(m\) 的彩色砖。那么这些砖一共占去 \(mk\) 个格子，剩下 \(n-mk\) 个灰格。由于同一种颜色的砖彼此没有区别，问题不在于区分单块砖，而在于两类对象沿整行的相对排列方式。
最方便的办法是做一次压缩：把每块长度为 \(m\) 的彩色砖都缩成一个长度为 1 的标记对象。这样每块砖都会少掉 \(m-1\) 个单位长度，因此压缩后的总长度变成
$$n-(m-1)k.$$
在这条压缩后的长度中，只需决定哪 \(k\) 个位置放置彩色对象，其余位置自然就是灰格。所以，恰好使用 \(k\) 块彩色砖的铺法数为
$$\binom{n-(m-1)k}{k}.$$
这个公式的适用范围是 \(0\le k\le \lfloor n/m\rfloor\)。
把所有可行的 \(k\) 加起来，就得到包含全灰方案在内的总数：
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
题目要求至少放一块彩色砖，所以要去掉 \(k=0\) 的那一项：
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
于是整道题的答案也可以直接写成
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$$
代码并不直接按组合公式求和，而是用一个非常短的动态规划来计算同一个数列。考虑长度为 \(n\) 的一行，观察最后一段。要么最后一个位置是灰格，那么前面 \(n-1\) 个位置可以是任意一种由 \(A_m(n-1)\) 计数的铺法；要么这一行以一块长度为 \(m\) 的彩色砖结尾，那么前面的 \(n-m\) 个位置可以是任意一种由 \(A_m(n-m)\) 计数的铺法。
因此得到递推
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
并配上初值
$$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0.$$
换句话说，当 \(0\le n<m\) 时，只存在全灰这一种铺法，所以 \(A_m(n)=1\)。对于 \(m=2\)，这就是平移后的 Fibonacci 关系 \(A_2(n)=F_{n+1}\)；而 \(m=3\) 与 \(m=4\) 虽然没有必要单独写闭式，但同样完全由这条线性递推决定。
题目中给出的短例子正好可以检验公式是否正确。
红砖 \((m=2)\) 的方案数为
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
第一项表示只放 1 块红砖时的 4 种位置选择，第二项表示放 2 块红砖时的 3 种排列方式。
绿砖 \((m=3)\) 的方案数为
$$B_3(5)=\binom{3}{1}=3.$$
蓝砖 \((m=4)\) 的方案数为
$$B_4(5)=\binom{2}{1}=2.$$
所以总数就是
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
这与题目给出的检验值完全一致，也清楚说明了三种颜色是分别计数、最后求和的。
定义
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
那么题目要求的就是 \(T(50)\)。实现的做法是分别用递推算出 \(A_2(50)\)、\(A_3(50)\)、\(A_4(50)\)，然后每个都减去 1 去掉全灰情况，再把三项相加。
C++、Python 和 Java 三个实现使用的是完全相同的单色动态规划。对于固定砖长 \(m\)，程序建立一个长度从 \(0\) 到 \(50\) 的表，把长度 0 的值设为 1，然后按长度递增依次填表。计算某个长度 \(n\) 时，先取“最后一个位置是灰格”的贡献，也就是长度 \(n-1\) 的值；如果 \(n\ge m\)，再加上“最后放一块长度为 \(m\) 的彩色砖”的贡献，也就是长度 \(n-m\) 的值。
得到长度 50 的表项后，程序减去 1，从而排除全灰铺法。接下来把同样的过程分别对 \(m=2\)、\(m=3\)、\(m=4\) 执行一遍，最后把三个单色结果相加。
C++ 实现还带了一个基于长度 5 示例的小型检查，而 Python 和 Java 版本直接计算长度 50 的情形。不过三者的核心算法完全一致，都是递推式 \(A_m(n)=A_m(n-1)+A_m(n-m)\)。
对固定的砖长 \(m\)，动态规划只需要填一张大小为 \(n+1\) 的表，所以时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)。在本题里 \(n=50\)，因此每一轮计算都非常小。
Problem 116 一共做三轮这样的计算，分别对应砖长 2、3、4。因此总时间复杂度是 \(O(3n)=O(n)\)，总空间复杂度仍然是 \(O(n)\)。由于颜色种类是固定常数，常数因子很小；对于 \(n=50\) 来说，整个计算几乎可以视为瞬时完成。
Есть ряд из 50 серых единичных клеток. В одной раскладке разрешено использовать плитки ровно одного несерого цвета: красные имеют длину 2, зеленые длину 3, синие длину 4. Серые клетки могут оставаться в любых местах, цветные плитки могут стоять вплотную друг к другу, смешивать цвета нельзя, а полностью серый ряд не засчитывается. Если \(B_m(n)\) обозначает число допустимых раскладок ряда длины \(n\) с серыми единичными клетками и плитками одной фиксированной длины \(m\), в которых используется хотя бы одна цветная плитка, то требуется вычислить
$$B_2(50)+B_3(50)+B_4(50).$$
Иными словами, задача распадается на три независимых одноцветных подсчета, которые суммируются только в самом конце.
Зафиксируем длину плитки \(m\in\{2,3,4\}\). Обозначим через \(A_m(n)\) полное число раскладок ряда длины \(n\), если разрешены серые клетки длины 1 и цветные плитки длины \(m\), причем полностью серый вариант тоже включается. Тогда \(B_m(n)=A_m(n)-1\). Ключевой объект здесь один и тот же: \(A_m(n)\). Его удобно описать двумя путями, совпадающими по значению: через точное число цветных плиток и через рекуррентное разбиение по правому краю ряда.
Если длина \(m\) выбрана, то любая допустимая раскладка состоит только из двух видов элементов:
$$\text{серая клетка длины }1,\qquad \text{цветная плитка длины }m.$$
Между цветными плитками не требуется обязательного промежутка. Две красные, две зеленые или две синие плитки могут стоять подряд. Именно поэтому эта задача проще, чем варианты с обязательными разделителями: единственное настоящее ограничение заключается в том, что суммарная длина должна равняться \(n\).
Пусть раскладка использует ровно \(k\) цветных плиток длины \(m\). Тогда они занимают \(mk\) клеток, а серых клеток остается \(n-mk\). Поскольку плитки одного цвета неразличимы, нужно считать не отдельные экземпляры, а лишь способы переплести два типа объектов вдоль ряда.
Удобнее всего применить сжатие: заменим каждую цветную плитку длины \(m\) на объект длины 1. При этом каждая такая плитка сокращает ряд на \(m-1\) клеток, так что длина сжатого ряда равна
$$n-(m-1)k.$$
В сжатом ряду остается только выбрать, какие \(k\) позиций заняты цветными объектами; остальные позиции будут серыми клетками. Поэтому число раскладок с ровно \(k\) цветными плитками равно
$$\binom{n-(m-1)k}{k}.$$
Формула применима при \(0\le k\le \lfloor n/m\rfloor\).
Если просуммировать по всем допустимым значениям \(k\), получится общее число раскладок, включая полностью серую:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Так как в условии требуется хотя бы одна цветная плитка, нужно удалить вклад \(k=0\):
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
Значит, полный ответ можно записать и так:
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$$
На практике реализации считают ту же величину при помощи небольшой динамики. Рассмотрим ряд длины \(n\) и посмотрим на его правый конец. Либо последняя клетка серая, и тогда первые \(n-1\) позиций образуют любую раскладку, учитываемую в \(A_m(n-1)\), либо ряд оканчивается одной цветной плиткой длины \(m\), и тогда первые \(n-m\) позиций образуют любую раскладку, учитываемую в \(A_m(n-m)\).
Отсюда получаем рекуррентное соотношение
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
с начальными условиями
$$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0.$$
Эквивалентно можно сказать, что для \(0\le n<m\) имеем просто \(A_m(n)=1\), поскольку существует только полностью серый ряд. При \(m=2\) получается сдвинутая последовательность Фибоначчи \(A_2(n)=F_{n+1}\); при \(m=3\) и \(m=4\) действует тот же самый линейный принцип.
Короткий пример из условия отлично проверяет формулы.
Для красных плиток \((m=2)\)
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
Первый член соответствует 4 способам поставить одну красную плитку, а второй член отвечает 3 способам поставить две красные плитки.
Для зеленых плиток \((m=3)\)
$$B_3(5)=\binom{3}{1}=3.$$
Для синих плиток \((m=4)\)
$$B_4(5)=\binom{2}{1}=2.$$
Следовательно, общий итог равен
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
что совпадает с известной контрольной величиной и сразу показывает: цвета считаются по отдельности, а не смешиваются в одной раскладке.
Определим
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
Тогда в задаче требуется найти \(T(50)\). Реализации вычисляют \(A_2(50)\), \(A_3(50)\) и \(A_4(50)\) по рекуррентной формуле, вычитают 1 из каждого результата, чтобы удалить полностью серый случай, и суммируют три одноцветных вклада.
Реализации на C++, Python и Java используют один и тот же динамический алгоритм для каждого цвета. Для выбранной длины плитки \(m\) они создают таблицу для длин \(0,1,\dots,50\), задают значение для длины 0 равным 1 и затем последовательно заполняют таблицу. При вычислении значения для длины \(n\) сначала берется вклад случая, когда ряд оканчивается серой клеткой, то есть значение для \(n-1\); если \(n\ge m\), затем добавляется вклад случая, когда ряд оканчивается одной цветной плиткой длины \(m\).
После получения значения для длины 50 программа вычитает 1, чтобы исключить полностью серую раскладку. Далее тот же расчет повторяется для \(m=2\), \(m=3\) и \(m=4\), после чего три результата суммируются.
В реализации на C++ есть еще небольшая проверка на примере длины 5, а версии на Python и Java сразу считают случай длины 50. Но во всех языках основной алгоритм один и тот же: рекуррентное соотношение \(A_m(n)=A_m(n-1)+A_m(n-m)\).
Для одной фиксированной длины \(m\) динамическое программирование заполняет одну таблицу размера \(n+1\). Поэтому время работы равно \(O(n)\), а память также составляет \(O(n)\). В рассматриваемой задаче \(n=50\), так что каждая отдельная проходка очень мала.
Problem 116 делает ровно три такие проходки, соответствующие длинам 2, 3 и 4. Значит, суммарная временная сложность равна \(O(3n)=O(n)\), а потребление памяти остается \(O(n)\). Поскольку набор цветов фиксирован, постоянный множитель мал; при \(n=50\) вычисление фактически мгновенно.
نبدأ بصف طوله 50 مكوَّن من مربعات رمادية وحدوية. في أي ترتيب واحد يُسمح باستعمال لون واحد فقط من البلاطات غير الرمادية: الحمراء طولها 2، والخضراء طولها 3، والزرقاء طولها 4. يمكن أن تبقى المربعات الرمادية في أي موضع، ويمكن أن تتجاور البلاطات الملوَّنة مباشرة، ولا يجوز خلط الألوان، كما أن الصف الرمادي بالكامل لا يُحسب. إذا رمزنا بـ \(B_m(n)\) إلى عدد الترتيبات الصحيحة لصف طوله \(n\) باستخدام مربعات رمادية طولها 1 وبلاطات ملوَّنة ذات طول ثابت \(m\)، مع اشتراط وجود بلاطة ملوَّنة واحدة على الأقل، فإن المطلوب هو
$$B_2(50)+B_3(50)+B_4(50).$$
إذن فالمسألة ليست عدًّا مختلط الألوان، بل هي ثلاثة مسائل مستقلة للون واحد ثم نجمع النتائج في النهاية.
لنثبت طول البلاطة \(m\in\{2,3,4\}\). ولْيكن \(A_m(n)\) عدد جميع طرق تبليط صف طوله \(n\) عند السماح بمربعات رمادية طولها 1 وبلاطات ملوَّنة طولها \(m\)، مع احتساب الحالة الرمادية بالكامل أيضًا. عندئذٍ يكون \(B_m(n)=A_m(n)-1\). الفكرة الأساسية هي وصف \(A_m(n)\) بطريقتين متكافئتين: عدٌّ مباشر بحسب عدد البلاطات الملوَّنة المستعملة، ثم علاقة عودية تُستخرج من النظر إلى نهاية الصف.
ما إن نثبت \(m\) حتى يصبح كل تبليط صحيح مكوَّنًا من نوعين فقط:
القطعتان المتاحتان هما مربع رمادي طوله 1 وبلاطة ملوَّنة طولها \(m\).
لا يوجد شرط يفرض وجود مربع رمادي فاصل بين البلاطات الملوَّنة. يمكن لبلاطتين حمراوين أو خضراوين أو زرقاوين أن تأتيَا متجاورتين. وهذه نقطة جوهرية؛ فهي السبب في أن هذه المسألة أبسط من مسائل التبليط التي تفرض فواصل إجبارية. القيد الحقيقي الوحيد هنا هو أن يبقى الطول الكلي مساويًا لـ \(n\).
افترض أن ترتيبًا ما يستعمل بالضبط \(k\) بلاطات ملوَّنة طول كل منها \(m\). هذه البلاطات تشغل معًا \(mk\) خلية، فيبقى \(n-mk\) مربعًا رماديًا. وبما أن البلاطات ذات اللون الواحد غير متميزة فيما بينها، فإن ما نعدّه فعليًا هو كيفية تعاقب هذين النوعين من العناصر على امتداد الصف.
الطريقة الأنظف هي حجة ضغط بسيطة: نضغط كل بلاطة ملوَّنة من طول \(m\) إلى طول 1. بهذا تختفي \(m-1\) خلية من كل بلاطة، فيصبح طول الصف المضغوط
$$n-(m-1)k.$$
وفي هذا الصف المضغوط لا يبقى إلا أن نختار أي \(k\) مواضع ستحتوي على العناصر الملوَّنة، بينما تكون المواضع الباقية مربعات رمادية. لذلك فإن عدد الترتيبات التي تستعمل بالضبط \(k\) بلاطات ملوَّنة يساوي
$$\binom{n-(m-1)k}{k}.$$
وتكون هذه الصيغة صحيحة عندما \(0\le k\le \lfloor n/m\rfloor\).
إذا جمعنا على جميع القيم المسموح بها لـ \(k\)، حصلنا على العدد الكلي بما في ذلك الصف الرمادي بالكامل:
$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
لكن المسألة تشترط استعمال بلاطة ملوَّنة واحدة على الأقل، لذا نحذف حد \(k=0\):
$$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$$
ومن ثم يمكن كتابة الجواب الكامل مباشرة على الصورة
$$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$$
التنفيذات لا تحسب مجموع معاملات ثنائية الحد مباشرة، بل تستخرج القيم نفسها ببرمجة ديناميكية قصيرة جدًا. انظر إلى صف طوله \(n\) وتأمل نهايته. إما أن تكون الخلية الأخيرة رمادية، وعندها تكون الخلايا \(n-1\) الأولى أي تبليط يُحصى في \(A_m(n-1)\)، أو أن ينتهي الصف ببلاطة ملوَّنة واحدة طولها \(m\)، وعندها تكون الخلايا \(n-m\) الأولى أي تبليط يُحصى في \(A_m(n-m)\).
وهذا يعطي العلاقة
$$A_m(n)=A_m(n-1)+A_m(n-m),$$
مع الشروط الابتدائية
$$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0.$$
وبصورة مكافئة، عندما \(0\le n<m\) لا يوجد إلا التبليط الرمادي الكامل، لذا يكون \(A_m(n)=1\). وفي الحالة \(m=2\) نحصل على متتالية فيبوناتشي المزاحة \(A_2(n)=F_{n+1}\)، أما في الحالتين \(m=3\) و\(m=4\) فتبقى الفكرة نفسها علاقة خطية بسيطة تُقيَّم مباشرة بالجدول.
المثال القصير الوارد في نص المسألة يصلح فحصًا مباشرًا للصيغ.
للبلاطات الحمراء \((m=2)\) نحصل على
$$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$$
الحد الأول يعدّ المواضع الأربعة الممكنة لبلاطة حمراء واحدة، والحد الثاني يعدّ الترتيبات الثلاثة الممكنة لبلاطتين حمراوين.
وللبلاطات الخضراء \((m=3)\)
$$B_3(5)=\binom{3}{1}=3.$$
وللبلاطات الزرقاء \((m=4)\)
$$B_4(5)=\binom{2}{1}=2.$$
إذن يكون المجموع
$$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$$
وهو تمامًا مقدار الفحص المعروف. كما يوضح المثال بجلاء أن كل لون يُعدّ على حدة ثم تُجمع المساهمات الثلاث.
لنعرّف
$$T(n)=B_2(n)+B_3(n)+B_4(n).$$
عندئذٍ تطلب المسألة قيمة \(T(50)\). وتحسب التطبيقات \(A_2(50)\) و\(A_3(50)\) و\(A_4(50)\) بالعلاقة العودية، ثم تطرح 1 من كل قيمة لإزالة الحالة الرمادية بالكامل، ثم تجمع النتائج الثلاثة.
تستخدم تطبيقات C++ وPython وJava الخوارزمية نفسها لكل لون. فلطول بلاطة ثابت \(m\)، تُنشأ مصفوفة للقيم عند الأطوال \(0,1,\dots,50\)، ويُجعل مقدار الطول 0 مساويًا لـ 1، ثم تُملأ المصفوفة تصاعديًا. عند حساب القيمة الخاصة بطول \(n\)، يبدأ التنفيذ بمساهمة الحالة التي تنتهي بمربع رمادي، أي قيمة \(n-1\)، ثم إذا كان \(n\ge m\) يضيف مساهمة الحالة التي تنتهي ببلاطة ملوَّنة طولها \(m\)، أي قيمة \(n-m\).
بعد الوصول إلى قيمة الطول 50، تطرح التطبيقات 1 لاستبعاد الصف الرمادي بالكامل. ثم يُعاد الحساب نفسه عند \(m=2\) و\(m=3\) و\(m=4\)، وفي النهاية تُجمع الأجوبة الثلاثة الخاصة بكل لون.
تتضمن نسخة C++ أيضًا فحصًا صغيرًا يعتمد مثال الطول 5، بينما تحسب نسختا Python وJava حالة الطول 50 مباشرة. ومع ذلك فالبنية الرياضية واحدة في جميع اللغات: العلاقة \(A_m(n)=A_m(n-1)+A_m(n-m)\).
لكل طول ثابت \(m\)، تملأ البرمجة الديناميكية جدولًا واحدًا حجمه \(n+1\)، ولذلك يكون الزمن \(O(n)\) وتكون الذاكرة \(O(n)\). وهنا \(n=50\)، لذا فكل تمريرة صغيرة جدًا.
تنفذ Problem 116 ثلاث تمريرات فقط، واحدة لكل طول في المجموعة \(\{2,3,4\}\). لذلك يكون الزمن الكلي \(O(3n)=O(n)\)، وتظل الذاكرة \(O(n)\). وبما أن عدد الألوان ثابت، فإن العامل الثابت صغير جدًا؛ وعند \(n=50\) يكون الحساب عمليًا فوريًا.