We consider a uniformly random permutation of the numbers \(1\) through \(100\). Among them, the marked objects are the \(25\) primes in that range. In the language of this problem, a prime is "foolish" when it does not return to its own position under the permutation.
The target event is therefore very specific: exactly \(22\) of those \(25\) prime-labelled items are misplaced, so exactly \(3\) primes are fixed points. The implementations are written for general parameters \((n,\;m,\;f)\), but for Problem 239 the relevant values are \(n=100\), \(m=25\), and \(f=3\).
The whole problem is a fixed-point counting question on a distinguished subset. Nothing special is required from the non-prime labels; once the prime labels satisfy the condition, every remaining label may be arranged freely. That observation is what makes a clean inclusion-exclusion count possible.
Let \(n\) be the total number of labels, let \(m\) be the number of marked labels, and let \(f\) be the number of marked labels that are allowed to stay fixed. For Problem 239, those marked labels are precisely the primes, so
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
We want permutations in which exactly \(f\) marked labels are fixed points and the remaining \(m-f\) marked labels are not. The non-marked labels are unrestricted except for filling the remaining places.
The first choice is purely combinatorial: decide which \(f\) marked labels are the ones that remain in their original positions. There are
$$\binom{m}{f}$$
ways to make that choice. After fixing those labels, both their positions and their values are no longer part of the count, so the problem shrinks to the remaining \(n-f\) slots.
Now let
$$b=m-f$$
be the number of marked labels that must avoid their own positions. In the actual problem, \(b=22\). If we ignore that restriction for a moment, there are \((n-f)!\) ways to arrange the remaining labels.
For inclusion-exclusion, choose a set of \(j\) among those \(b\) forbidden marked labels and pretend that all of them are fixed after all. Once those \(j\) extra positions are forced, the remaining objects can be permuted arbitrarily, giving
$$ (n-f-j)! $$
arrangements. There are \(\binom{b}{j}\) ways to choose the set, so the number of valid completions is
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$$
Multiplying by the earlier choice of which marked labels stay fixed gives the exact count
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
Since all \(n!\) permutations are equally likely, the desired probability is just \(A(n,m,f)/n!\). For this problem that becomes
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
This is the exact probability that exactly three primes are fixed and the other twenty-two are foolish. The implementations evaluate this normalized sum directly rather than forming the huge integer count first.
The solution files do not repeatedly compute factorials and binomial coefficients from scratch inside the alternating sum. Instead they use the normalized term
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
so that
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
The first term is
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
and adjacent terms satisfy the simple ratio
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
That recurrence is exactly what the C++, Python, and Java implementations update inside their main loop. It keeps the computation compact and avoids manufacturing enormous intermediate factorial values only to divide them away again a moment later.
A smaller example shows the same logic more transparently. Suppose \(n=8\), \(m=3\), and we want exactly \(f=1\) marked label fixed. Then \(b=2\). First choose which marked label is fixed: \(\binom{3}{1}=3\) choices.
After that, \(7\) labels remain. The other two marked labels must avoid their own positions. Inclusion-exclusion gives
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
Since \(8!=40320\), the probability is
$$\frac{11160}{40320}=\frac{31}{112}.$$
Problem 239 is exactly the same argument, just with \(100\) total labels, \(25\) marked primes, \(3\) fixed primes, and \(22\) forbidden prime fixed points.
The implementations start from the general parameters \(n\), \(m\), and the number of misplaced marked labels. From that they derive \(f=m-r\), the number of marked fixed points that must occur. For Problem 239 this means converting "22 foolish primes" into "3 fixed prime-labelled items."
Next, they compute \(\binom{m}{f}\) multiplicatively, one factor at a time. The alternating sum is then evaluated through the recurrence for \(T_j\): the code builds \(T_0\) by dividing by \(n\), \(n-1\), and so on for exactly \(f\) factors, and each later term is obtained from the previous one by multiplying with the rational ratio above. The running sum therefore mirrors the inclusion-exclusion formula term by term.
Finally, the sum is multiplied by \(\binom{m}{f}\) and formatted as a decimal with twelve digits after the point. The C++ implementation also performs small-instance checks: it compares the inclusion-exclusion count against exact enumeration on tiny cases and verifies on a sample input that summing the probabilities over all possible numbers of fixed marked labels gives total mass \(1\).
The binomial coefficient \(\binom{m}{f}\) is computed in \(O(\min(f,m-f))\) arithmetic steps, and the alternating sum has exactly \(b+1=m-f+1\) terms. So the overall running time is \(O(m)\), with constant extra space.
For the actual Project Euler instance this is tiny: \(f=3\) and \(b=22\), so the probability comes from only \(23\) inclusion-exclusion terms. The mathematical work is in deriving the formula; the numerical evaluation itself is very light.
Wir betrachten eine gleichverteilte Zufallspermutation der Zahlen \(1\) bis \(100\). Die ausgezeichneten Objekte sind die \(25\) Primzahlen in diesem Bereich. Im Sinn dieser Aufgabe ist eine Primzahl "foolish", wenn ihr markiertes Element nicht auf seine ursprüngliche Position zurückkehrt.
Gesucht ist also die Wahrscheinlichkeit, dass genau \(22\) dieser \(25\) primmarkierten Elemente fehlplatziert sind. Gleichbedeutend damit ist: Genau \(3\) Primzahlen sind Fixpunkte. Die Implementierungen sind allgemein für \((n,\;m,\;f)\) formuliert, aber für Problem 239 gilt \(n=100\), \(m=25\) und \(f=3\).
Der Kern ist eine Fixpunktzählung auf einer ausgezeichneten Teilmenge. Für die nicht markierten Zahlen gibt es keine individuelle Nebenbedingung; sobald die Primzahlen die richtige Eigenschaft erfüllen, dürfen alle übrigen Elemente beliebig angeordnet werden. Dadurch wird Inklusion-Exklusion direkt anwendbar.
Bezeichne mit \(n\) die Gesamtzahl der Elemente, mit \(m\) die Zahl der markierten Elemente und mit \(f\) die Zahl der markierten Elemente, die Fixpunkte sein sollen. In dieser Aufgabe sind die markierten Elemente gerade die Primzahlen, also
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
Gesucht sind Permutationen, in denen genau \(f\) markierte Elemente fix bleiben und die restlichen \(m-f\) markierten Elemente gerade keine Fixpunkte sind. Alle nicht markierten Elemente sind darüber hinaus frei.
Zuerst entscheidet man, welche \(f\) markierten Elemente überhaupt an ihrer Stelle bleiben. Dafür gibt es
$$\binom{m}{f}$$
Möglichkeiten. Danach sind diese Positionen fest vergeben, und das Problem reduziert sich auf die verbleibenden \(n-f\) Plätze.
Setze
$$b=m-f.$$
Im echten Problem ist also \(b=22\). Diese \(b\) markierten Elemente dürfen nicht auf ihre eigenen Positionen zurückkehren. Wenn man diese Bedingung zunächst ignoriert, gibt es \((n-f)!\) Anordnungen der restlichen Elemente.
Für Inklusion-Exklusion wählt man nun \(j\) dieser \(b\) verbotenen Fixpunkte aus und tut so, als wären sie doch fest vorgeschrieben. Sind diese \(j\) zusätzlichen Positionen fixiert, bleiben
$$ (n-f-j)! $$
freie Anordnungen übrig. Da es \(\binom{b}{j}\) Auswahlmöglichkeiten gibt, folgt für die gültigen Fortsetzungen
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$$
Mit der anfänglichen Wahl der wirklich festen Primzahlen erhält man die exakte Anzahl
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
Da alle \(n!\) Permutationen gleich wahrscheinlich sind, ist die gesuchte Wahrscheinlichkeit \(A(n,m,f)/n!\). Für die konkrete Aufgabe ergibt sich damit
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
Das ist genau die Wahrscheinlichkeit, dass drei Primzahlen Fixpunkte sind und die übrigen zweiundzwanzig primmarkierten Elemente fehlplatziert werden. Die Implementierungen werten diese normierte Summe direkt aus.
Die Lösungsprogramme berechnen innerhalb der alternierenden Summe nicht jedes Mal Fakultäten und Binomialkoeffizienten von Grund auf neu. Stattdessen verwenden sie den normierten Term
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
sodass
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
Der erste Term ist
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
und benachbarte Terme erfüllen
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
Genau diese Rekurrenz wird in C++, Python und Java iterativ umgesetzt. So vermeidet man riesige Zwischenfakultäten, die am Ende ohnehin sofort wieder wegdividiert würden.
Ein kleines Beispiel zeigt dieselbe Idee klarer. Nimm \(n=8\), \(m=3\) und fordere genau \(f=1\) fixes markiertes Element. Dann ist \(b=2\). Zuerst wählt man das feste markierte Element in \(\binom{3}{1}=3\) Varianten.
Danach bleiben \(7\) Elemente übrig, und die beiden anderen markierten Elemente dürfen nicht auf ihren eigenen Positionen landen. Inklusion-Exklusion liefert
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
Weil \(8!=40320\) ist, erhält man die Wahrscheinlichkeit
$$\frac{11160}{40320}=\frac{31}{112}.$$
Problem 239 ist exakt dieselbe Rechnung mit \(100\) Elementen, \(25\) Primzahlen, \(3\) erlaubten Prim-Fixpunkten und \(22\) verbotenen Prim-Fixpunkten.
Die Implementierungen starten mit den allgemeinen Parametern \(n\), \(m\) und der Zahl der fehlplatzierten markierten Elemente. Daraus wird \(f=m-r\) bestimmt, also die Zahl der markierten Fixpunkte. Für Problem 239 wird so die Formulierung "22 foolish primes" in "3 feste primmarkierte Elemente" übersetzt.
Anschließend wird \(\binom{m}{f}\) multiplikativ berechnet. Die alternierende Summe wird nicht als Sammlung großer Fakultäten aufgebaut, sondern über die Rekurrenz für \(T_j\): Zunächst entsteht \(T_0\) durch Division durch \(n\), \(n-1\) und so weiter für genau \(f\) Faktoren; jeder weitere Summand wird dann mit dem rationalen Quotienten aus der vorherigen Zeile erzeugt. Damit bildet der Code die Inklusion-Exklusion-Formel termweise nach.
Am Ende wird mit \(\binom{m}{f}\) multipliziert und das Ergebnis mit zwölf Nachkommastellen ausgegeben. Die C++-Implementierung enthält zusätzlich Plausibilitätsprüfungen auf kleinen Instanzen: Sie vergleicht die Formel mit exakter Enumeration und prüft an einem Beispiel, dass sich die Wahrscheinlichkeiten über alle möglichen Zahlen markierter Fixpunkte zu \(1\) summieren.
Der Binomialkoeffizient \(\binom{m}{f}\) kostet \(O(\min(f,m-f))\) Rechenschritte, und die alternierende Summe besitzt genau \(b+1=m-f+1\) Terme. Insgesamt ergibt sich also Laufzeit \(O(m)\) bei \(O(1)\) Zusatzspeicher.
Im konkreten Euler-Fall ist das winzig: \(f=3\) und \(b=22\), also nur \(23\) Summanden. Die eigentliche Schwierigkeit liegt in der Herleitung der Zählformel, nicht in ihrer numerischen Auswertung.
\(1\)'den \(100\)'e kadar sayıların eş olasılıklı rastgele bir permütasyonu ele alınıyor. Bu kümede özel olarak izlenen öğeler, \(100\)'e kadar olan \(25\) asal sayıdır. Problemde bir asalın "foolish" olması, asal etiketli o öğenin kendi başlangıç konumuna dönmemesi anlamına gelir.
Dolayısıyla aranan olay şudur: Bu \(25\) asal etiketli öğeden tam \(22\) tanesi yanlış yerde olsun. Bu da eşdeğer olarak tam \(3\) asalin sabit nokta olması demektir. C++, Python ve Java çözümleri genel \((n,\;m,\;f)\) parametreleriyle yazılmıştır; Problem 239 için \(n=100\), \(m=25\) ve \(f=3\) kullanılır.
Problemin özü, seçilmiş bir alt kümede sabit nokta saymaktır. Asal olmayan etiketler için ayrı bir yasak yoktur; asallarla ilgili şart sağlandıktan sonra kalan etiketler boş yerleri serbestçe doldurabilir. Bu yüzden doğru araç doğrudan dahil etme-dışlama ilkesidir.
\(n\) toplam etiket sayısı, \(m\) işaretli etiket sayısı ve \(f\) de sabit kalmasına izin verilen işaretli etiket sayısı olsun. Bu problemde işaretli etiketler asallardır; dolayısıyla
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
İstediğimiz permütasyonlarda tam \(f\) işaretli etiket sabit nokta olacak, geri kalan \(m-f\) işaretli etiket ise sabit nokta olmayacaktır. İşaretli olmayan etiketler için bundan başka bir kısıt yoktur.
Önce gerçekten yerinde kalacak \(f\) asal etiketin hangileri olduğunu seçeriz. Bunun sayısı
$$\binom{m}{f}$$
kadardır. Bu seçim yapıldıktan sonra o konumlar ve o etiketler artık problemden düşer; geriye \(n-f\) konumluk daha küçük bir düzenleme kalır.
Şimdi
$$b=m-f$$
olsun. Gerçek problemde \(b=22\)'dir. Bu \(b\) asal etiketin her biri kendi yerine gelmekten kaçınmak zorundadır. Bu yasağı bir an için yok sayarsak, kalan etiketlerin diziliş sayısı \((n-f)!\) olur.
Dahil etme-dışlama için, yasaklı bu \(b\) asaldan \(j\) tanesini seçip sanki onlar da yerinde kalmak zorundaymış gibi davranırız. Bu \(j\) ek sabitleme yapıldığında, geri kalan serbest yerleşim sayısı
$$ (n-f-j)! $$
olur. Böyle kümelerin sayısı \(\binom{b}{j}\) olduğundan, geçerli tamamlama sayısı
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!$$
çıkar. Bunu ilk seçimle çarptığımızda tam sayım formülü elde edilir:
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
Tüm \(n!\) permütasyonlar eş olasılıklı olduğu için aranan olasılık \(A(n,m,f)/n!\) olur. Bu problemde formül doğrudan
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
şeklindedir. Yani tam üç asal sabit nokta olacak ve diğer yirmi iki asal kendi yerine dönmeyecektir. Kodun yaptığı iş, tam olarak bu normalize edilmiş toplamı hesaplamaktır.
Çözüm dosyaları, alternanslı toplamın her teriminde faktöriyel ve kombinasyonları baştan kurmaz. Bunun yerine
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!}$$
terimini kullanırlar; böylece
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j$$
olur. İlk terim
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i}$$
ve ardışık terimler arasındaki oran
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}$$
şeklindedir. C++, Python ve Java çözümlerinin ana döngüsü tam olarak bu oranı uygular. Böylece dev ara faktöriyel değerleri üretip sonra birbirine bölen bir yöntem yerine çok daha dengeli bir sayısal akış elde edilir.
Küçük bir örnek aynı mantığı daha görünür kılar. Diyelim ki \(n=8\), \(m=3\) ve tam \(f=1\) işaretli etiket sabit nokta olsun. O zaman \(b=2\). Önce sabit kalacak işaretli etiketi \(\binom{3}{1}=3\) şekilde seçeriz.
Sonra \(7\) etiket kalır ve öteki iki işaretli etiket kendi yerlerine gelemez. Dahil etme-dışlama sayımı
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160$$
verir. \(8!=40320\) olduğuna göre olasılık
$$\frac{11160}{40320}=\frac{31}{112}$$
olur. Problem 239'da yapılan şey bunun \(100\) eleman, \(25\) asal, \(3\) izinli asal sabit nokta ve \(22\) yasaklı asal sabit nokta için uygulanmış halidir.
Uygulamalar önce genel girişleri alır: toplam etiket sayısı, işaretli etiket sayısı ve yanlış yerde olması istenen işaretli etiket sayısı. Buradan \(f=m-r\) hesaplanır. Problem 239 bağlamında bu, "22 foolish primes" ifadesini "3 asal sabit nokta" biçimine dönüştürür.
Sonra \(\binom{m}{f}\) çarpımsal olarak hesaplanır. Alternanslı toplam için önce \(T_0\) terimi üretilir; bu, \(n\), \(n-1\), ... diye tam \(f\) kez bölerek elde edilir. Daha sonraki her terim, bir önceki terimin üzerine yukarıdaki oranla güncellenir. Böylece kod, dahil etme-dışlama formülünü doğrudan ama verimli biçimde işler.
Son aşamada toplam, \(\binom{m}{f}\) ile çarpılır ve sonuç ondalık biçimde on iki basamakla yazdırılır. C++ uygulaması ayrıca küçük örneklerde formülü tam sayım ve kaba kuvvet permütasyon taramasıyla karşılaştırır; ayrıca bir örnek parametre için tüm olasılıkların toplamının \(1\) olduğunu kontrol eder.
\(\binom{m}{f}\) hesabı \(O(\min(f,m-f))\) adım sürer; alternanslı toplam ise tam \(b+1=m-f+1\) terime sahiptir. Bu yüzden toplam süre \(O(m)\), ek bellek ise \(O(1)\)'dir.
Gerçek Project Euler verilerinde iş daha da küçüktür: \(f=3\) ve \(b=22\) olduğundan yalnızca \(23\) terim toplanır. Zorluk hesaplama maliyetinde değil, doğru kombinatoryal modeli kurmaktadır.
Se toma una permutacion aleatoria uniforme de los numeros del \(1\) al \(100\). Los objetos distinguidos son los \(25\) numeros primos de ese conjunto. En el contexto del problema, un primo es "foolish" cuando el elemento etiquetado con ese primo no vuelve a su posicion original.
Por tanto, el evento pedido es: exactamente \(22\) de esos \(25\) elementos primos quedan fuera de su sitio. Eso equivale a decir que exactamente \(3\) primos son puntos fijos. Las implementaciones estan escritas para parametros generales \((n,\;m,\;f)\), pero en el problema concreto se usa \(n=100\), \(m=25\) y \(f=3\).
Todo se reduce a contar puntos fijos dentro de un subconjunto distinguido. Los elementos no primos no tienen una restriccion individual; una vez satisfecha la condicion sobre los primos, los demas pueden ocupar libremente las posiciones restantes. Esa separacion es exactamente lo que permite aplicar inclusion-exclusion de forma limpia.
Sea \(n\) el numero total de etiquetas, \(m\) el numero de etiquetas marcadas y \(f\) el numero de etiquetas marcadas que si deben quedar fijas. En este problema las marcadas son justamente las primas, asi que
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
Buscamos permutaciones donde exactamente \(f\) etiquetas marcadas sean puntos fijos y las otras \(m-f\) no lo sean. Fuera de eso, las etiquetas no marcadas no tienen ninguna condicion especial.
El primer paso es decidir cuales son las \(f\) etiquetas marcadas que si quedan en su lugar. Eso puede hacerse de
$$\binom{m}{f}$$
formas. Una vez fijadas, esas posiciones dejan de intervenir y el problema se traslada a los \(n-f\) lugares restantes.
Definamos
$$b=m-f.$$
En la instancia real, \(b=22\). Esos \(b\) elementos primos no pueden volver a sus propias posiciones. Si ignoramos temporalmente esa prohibicion, hay \((n-f)!\) maneras de ordenar lo que queda.
Ahora elegimos un subconjunto de \(j\) de esos \(b\) primos prohibidos y fingimos que si estan fijos. Con esos \(j\) puntos adicionales forzados, el resto puede permutarse de
$$ (n-f-j)! $$
maneras. Como hay \(\binom{b}{j}\) formas de elegir el subconjunto, inclusion-exclusion da
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!$$
completaciones validas. Multiplicando por la eleccion inicial de los primos fijos obtenemos el conteo exacto
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
Como todas las \(n!\) permutaciones son equiprobables, la probabilidad buscada es \(A(n,m,f)/n!\). En este problema queda
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
Ese es el valor exacto de la probabilidad de que haya exactamente tres primos fijos y veintidos primos "foolish". Las implementaciones trabajan directamente con esta forma normalizada.
Los programas no recalculan factoriales y combinaciones gigantes en cada termino. En su lugar usan
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
de modo que
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
El termino inicial es
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
y los terminos consecutivos satisfacen
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
Esa igualdad es exactamente la actualizacion que realizan las implementaciones en C++, Python y Java. La ventaja es que evita fabricar factoriales enormes para luego cancelarlos inmediatamente.
Un ejemplo pequeno deja la idea al descubierto. Supongamos \(n=8\), \(m=3\) y queremos exactamente \(f=1\) etiqueta marcada fija. Entonces \(b=2\). Primero elegimos esa etiqueta fija en \(\binom{3}{1}=3\) maneras.
Quedan \(7\) etiquetas por colocar, y las otras dos marcadas no pueden caer en su sitio propio. Inclusion-exclusion produce
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
Dado que \(8!=40320\), la probabilidad es
$$\frac{11160}{40320}=\frac{31}{112}.$$
Problem 239 repite exactamente esta cuenta, solo que con \(100\) elementos, \(25\) primos marcados, \(3\) puntos fijos primos permitidos y \(22\) puntos fijos primos prohibidos.
Las implementaciones reciben los parametros generales \(n\), \(m\) y el numero de elementos marcados mal colocados. A partir de eso calculan \(f=m-r\), es decir, cuantos puntos fijos marcados deben aparecer. En Problem 239 eso convierte "22 foolish primes" en "3 elementos primos fijados".
Despues calculan \(\binom{m}{f}\) de forma multiplicativa. La suma alternante se evalua con la recurrencia de \(T_j\): primero se construye \(T_0\) dividiendo por \(n\), \(n-1\), etc., exactamente \(f\) veces; luego cada termino nuevo se obtiene multiplicando el anterior por la razon racional mostrada arriba. Asi el codigo sigue el desarrollo de inclusion-exclusion sin recurrir a factoriales gigantes.
Al final, la suma se multiplica por \(\binom{m}{f}\) y se imprime como decimal con doce cifras. La implementacion en C++ ademas valida la formula en casos pequenos, comparandola con conteos exactos y con una enumeracion exhaustiva, y verifica en un ejemplo que la masa total de probabilidad sea \(1\).
El calculo de \(\binom{m}{f}\) cuesta \(O(\min(f,m-f))\), y la suma alternante tiene exactamente \(b+1=m-f+1\) terminos. Por tanto, el tiempo total es \(O(m)\) y la memoria extra es \(O(1)\).
En la instancia real eso es minimo: \(f=3\) y \(b=22\), asi que solo se suman \(23\) terminos. La dificultad real del problema es combinatoria, no computacional.
题目研究的是 \(1\) 到 \(100\) 的一个等概率随机排列。其中真正需要特别追踪的对象，是这 \(100\) 个数里那 \(25\) 个素数。按照这道题的语境，一个素数是 “foolish”，意思就是这个素数标签没有回到它自己的原始位置。
因此，题目要求的事件可以精确表述为：这 \(25\) 个素数标签中，恰好有 \(22\) 个没有固定，也就是恰好只有 \(3\) 个素数是排列的固定点。三份实现都写成了一般参数 \((n,\;m,\;f)\) 的形式；对 Problem 239 来说，代入的是 \(n=100\)、\(m=25\)、\(f=3\)。
这道题本质上不是在数整个排列的所有结构，而是在数一个被标记子集中的固定点个数。非素数标签并没有各自额外的限制；只要素数标签满足条件，其余标签怎样填满剩余位置都可以。正因为限制只落在被标记的那部分对象上，容斥原理才能非常自然地展开。
设 \(n\) 是总标签数，\(m\) 是被标记标签数，\(f\) 是最终允许保持固定的被标记标签数。对本题而言，被标记标签正是素数，所以
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
我们要找的排列满足：恰好有 \(f\) 个被标记标签是固定点，而其余 \(m-f\) 个被标记标签都不能固定。除此之外，非标记标签没有单独限制。
第一步很直接：先决定是哪 \(f\) 个素数标签留在原位。这个选择有
$$\binom{m}{f}$$
种可能。选定之后，这些位置和这些标签就都已经处理完了，问题规模随之缩小到剩下的 \(n-f\) 个位置。
再令
$$b=m-f.$$
在实际题目里，\(b=22\)。这 \(b\) 个素数标签必须全部避开它们自己的位置。如果暂时忽略这个限制，那么剩余标签的排法共有 \((n-f)!\) 种。
接着做标准的容斥：从这 \(b\) 个“本来不允许固定”的素数中任选 \(j\) 个，假装它们现在被强制固定。这样一来，又额外锁定了 \(j\) 个位置，于是剩下的对象可以任意排列，排法数就是
$$ (n-f-j)! $$
种。这样的 \(j\) 元子集共有 \(\binom{b}{j}\) 个，因此容斥给出合法完成数
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$$
再乘上前面“选哪 \(f\) 个素数固定”的因子，就得到精确计数公式
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
由于所有 \(n!\) 个排列等可能，所求概率就是 \(A(n,m,f)/n!\)。代入本题参数后得到
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
这正是“恰好 3 个素数固定、另外 22 个素数不固定”的精确概率。实现代码也是直接求这个已经除以 \(100!\) 的归一化表达式，而不是先去构造庞大的整数计数再做除法。
代码没有在交错求和的每一项里反复计算巨大的阶乘和组合数，而是把单项写成
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
于是
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
首项为
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
相邻两项之间满足简单的比例关系
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
这正是 C++、Python 和 Java 三份实现中主循环所做的更新。这样做的好处是显而易见的：不需要先生成极大的阶乘，再在下一步把它们彼此消掉，数值尺度也更容易控制。
用小参数可以更直观地看到同一套推导。假设 \(n=8\)、\(m=3\)，并要求恰好 \(f=1\) 个被标记标签固定。那么 \(b=2\)。首先，要选出哪个被标记标签固定，共有 \(\binom{3}{1}=3\) 种选法。
选完后还剩 \(7\) 个标签要排，而另外两个被标记标签都不能回到自己的位置。容斥计算为
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
由于 \(8!=40320\)，对应概率就是
$$\frac{11160}{40320}=\frac{31}{112}.$$
Problem 239 完全是同样的结构，只不过把参数换成了 \(100\) 个总元素、\(25\) 个素数标签、\(3\) 个允许固定的素数，以及 \(22\) 个必须避免固定的素数。
实现先从一般输入出发：总数 \(n\)、标记数 \(m\)、以及要求错位的标记数。然后由 \(f=m-r\) 推出必须固定的标记数。对 Problem 239 来说，这一步就是把 “22 foolish primes” 转换成 “3 个素数固定点”。
接下来，代码用乘法方式计算 \(\binom{m}{f}\)。交错和部分则通过上面的 \(T_j\) 递推完成：先把 \(T_0\) 写成连续几个倒数的乘积，再用一条短小的有理比值公式从上一项推出下一项。这样，整段程序就精确对应了容斥推导，但不会真的去展开巨大的阶乘表达式。
最后，把交错和乘上 \(\binom{m}{f}\)，并按十二位小数格式输出。C++ 实现还额外做了小规模校验：它在若干很小的参数上把公式结果与精确计数、穷举排列进行比对，并检查某个样例中所有可能固定点个数的概率总和确实为 \(1\)。
\(\binom{m}{f}\) 的计算需要 \(O(\min(f,m-f))\) 步，而交错和一共只有 \(b+1=m-f+1\) 项，所以总时间复杂度是 \(O(m)\)，额外空间复杂度是 \(O(1)\)。
对本题实际参数来说，这几乎是瞬间完成的：\(f=3\)、\(b=22\)，因此主求和只有 \(23\) 项。真正需要思考的是组合计数如何建立，而不是程序跑得够不够快。
Рассматривается равновероятная случайная перестановка чисел от \(1\) до \(100\). Выделенное подмножество состоит из \(25\) простых чисел в этом диапазоне. В терминах задачи простое число считается "foolish", если элемент с этим простым ярлыком не возвращается на свое исходное место.
Следовательно, интересующее событие формулируется так: ровно \(22\) из этих \(25\) простых элементов стоят не на своих местах. Эквивалентно, ровно \(3\) простых числа являются неподвижными точками. Реализации написаны в общем виде для параметров \((n,\;m,\;f)\); для Problem 239 подставляются \(n=100\), \(m=25\) и \(f=3\).
Суть задачи состоит в подсчете числа неподвижных точек внутри выделенного подмножества. Для непростых меток нет индивидуальных ограничений: как только условие на простые выполнено, остальные элементы могут быть расставлены произвольно. Именно поэтому здесь естественно работает принцип включения-исключения.
Пусть \(n\) обозначает общее число меток, \(m\) - число отмеченных меток, а \(f\) - число отмеченных меток, которым разрешено остаться на месте. В этой задаче отмеченные метки - это простые числа, поэтому
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
Нам нужны такие перестановки, в которых ровно \(f\) отмеченных элементов являются неподвижными точками, а остальные \(m-f\) отмеченных элементов неподвижными точками не являются. Больше никаких условий на неотмеченные элементы нет.
Сначала нужно выбрать, какие именно \(f\) отмеченных элементов будут зафиксированы. Это можно сделать
$$\binom{m}{f}$$
способами. После такого выбора соответствующие позиции уже обработаны, и задача сокращается до оставшихся \(n-f\) мест.
Обозначим
$$b=m-f.$$
В реальной задаче \(b=22\). Эти \(b\) простых меток обязаны избежать своих собственных позиций. Если временно забыть об этом запрете, оставшиеся элементы можно переставить \((n-f)!\) способами.
Теперь выбираем \(j\) из этих \(b\) запрещенных неподвижных точек и делаем вид, что они все-таки должны быть зафиксированы. Тогда дополнительно закрепляются \(j\) позиций, а остальные элементы можно переставить
$$ (n-f-j)! $$
способами. Так как выбрать такое множество можно \(\binom{b}{j}\) способами, получаем по принципу включения-исключения число допустимых продолжений
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$$
Умножая на начальный выбор фиксированных простых, получаем точную формулу подсчета:
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
Поскольку все \(n!\) перестановок равновероятны, искомая вероятность равна \(A(n,m,f)/n!\). Для этой задачи она принимает вид
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
Это и есть точная вероятность того, что ровно три простых останутся на месте, а остальные двадцать два окажутся "foolish". Реализации вычисляют сразу эту нормированную сумму.
Внутри знакопеременной суммы программы не пересчитывают каждый раз большие факториалы и биномиальные коэффициенты с нуля. Вместо этого используется нормированный член
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
так что
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
Начальный член равен
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
а соседние члены связаны формулой
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
Именно эту короткую рекуррентную связь и обновляют реализации на C++, Python и Java. Такой подход избегает огромных промежуточных чисел, которые в конце все равно сократились бы при делении на \(n!\).
Возьмем маленькие параметры \(n=8\), \(m=3\) и потребуем ровно \(f=1\) фиксированный отмеченный элемент. Тогда \(b=2\). Сначала выбираем, какой именно отмеченный элемент останется на месте: \(\binom{3}{1}=3\) варианта.
После этого остается расставить \(7\) элементов, причем два других отмеченных не должны попасть на свои места. По включению-исключению получаем
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
Так как \(8!=40320\), вероятность равна
$$\frac{11160}{40320}=\frac{31}{112}.$$
В Problem 239 происходит ровно тот же подсчет, только с параметрами \(100\), \(25\), \(3\) и \(22\).
Сначала реализации читают общие параметры: \(n\), число отмеченных элементов \(m\) и число отмеченных элементов, которые должны оказаться не на месте. Из этого вычисляется \(f=m-r\), то есть число отмеченных неподвижных точек. В случае Problem 239 это переводит условие "22 foolish primes" в "3 фиксированных простых".
Далее \(\binom{m}{f}\) считается в мультипликативной форме. Знакочередующаяся сумма вычисляется через рекурсию для \(T_j\): сначала строится \(T_0\) как произведение нескольких обратных множителей, а затем каждый следующий член получается из предыдущего умножением на рациональный коэффициент. Тем самым код буквально следует формуле включения-исключения, но без громоздких факториальных вычислений.
После этого сумма умножается на \(\binom{m}{f}\), а ответ выводится в виде десятичной дроби с двенадцатью знаками после запятой. Реализация на C++ вдобавок делает проверки на маленьких примерах: сравнивает формулу с точным перебором и контролирует, что для одного тестового набора суммарная вероятность по всем возможным значениям числа фиксированных отмеченных элементов равна \(1\).
Вычисление \(\binom{m}{f}\) требует \(O(\min(f,m-f))\) арифметических шагов, а знакопеременная сумма содержит ровно \(b+1=m-f+1\) членов. Следовательно, общая асимптотика равна \(O(m)\) по времени и \(O(1)\) по дополнительной памяти.
Для реального экземпляра это совсем мало: \(f=3\) и \(b=22\), то есть в основной сумме всего \(23\) члена. Сложность задачи здесь математическая, а не вычислительная.
المسألة تتعامل مع تبديل عشوائي منتظم للاعداد من \(1\) إلى \(100\). العناصر المميزة هنا هي \(25\) عددًا أوليًا ضمن هذه المجموعة. وفي سياق المسألة يكون العدد الأولي "foolish" عندما لا يعود العنصر الموسوم بهذا العدد إلى موضعه الأصلي.
إذن الحدث المطلوب محدد بدقة: بالضبط \(22\) من هذه العناصر الأولية الخمسة والعشرين تكون في غير موضعها. وهذا يكافئ القول إن بالضبط \(3\) أعداد أولية هي نقاط تثبيت. الحلول في C++ وPython وJava مكتوبة بصيغة عامة للمعلمات \((n,\;m,\;f)\)، أما في Problem 239 فنأخذ \(n=100\) و\(m=25\) و\(f=3\).
جوهر المسألة هو عد نقاط التثبيت داخل مجموعة مميزة فقط. العناصر غير الأولية لا تملك قيدًا فرديًا خاصًا؛ ما إن يتحقق شرط العناصر الأولية حتى تستطيع بقية العناصر شغل المواقع المتبقية بحرية. ولهذا يصبح مبدأ الشمول والاستبعاد هو الأداة الطبيعية للحل.
لنرمز إلى عدد العناصر الكلي بـ \(n\)، وعدد العناصر المعلَّمة بـ \(m\)، وعدد العناصر المعلَّمة المسموح لها بالبقاء ثابتة بـ \(f\). في هذه المسألة العناصر المعلَّمة هي الأعداد الأولية نفسها، ولذلك
$$n=100,\qquad m=25,\qquad f=25-22=3.$$
نحن نريد تبديلات يكون فيها بالضبط \(f\) من العناصر المعلَّمة نقاط تثبيت، بينما العناصر \(m-f\) الأخرى المعلَّمة يجب ألا تكون نقاط تثبيت. أما العناصر غير المعلَّمة فلا يوجد عليها قيد إضافي.
الخطوة الأولى هي اختيار أي \(f\) من العناصر الأولية ستبقى في مواضعها. عدد هذه الاختيارات هو
$$\binom{m}{f}.$$
بعد تثبيت هذه العناصر، تصبح مواضعها وقيمها محسومة، ويتقلص العد إلى الترتيب على \(n-f\) موضعًا متبقيًا.
لنضع
$$b=m-f.$$
في المسألة الفعلية نحصل على \(b=22\). هذه العناصر الأولية \(b\) يجب أن تتجنب مواضعها الأصلية. وإذا تجاهلنا هذا القيد مؤقتًا، فعدد ترتيبات العناصر الباقية يساوي \((n-f)!\).
الآن نختار \(j\) عنصرًا من هذه العناصر الأولية الممنوع تثبيتها، ونتظاهر بأنها أصبحت ثابتة على الرغم من المنع. عند فرض هذه \(j\) التثبيتات الإضافية، يبقى عدد الترتيبات الحرة مساويًا لـ
$$ (n-f-j)! $$
طريقة. وبما أن عدد طرق اختيار هذه المجموعة هو \(\binom{b}{j}\)، فإن مبدأ الشمول والاستبعاد يعطينا عدد الإكمالات الصحيحة
$$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$$
ثم نضرب في اختيار العناصر الأولية الثابتة أصلًا فنحصل على صيغة العد الدقيقة:
$$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$$
لأن جميع التبديلات وعددها \(n!\) متساوية الاحتمال، فإن الاحتمال المطلوب هو \(A(n,m,f)/n!\). وبالتعويض في هذه المسألة نحصل على
$$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$$
وهذا هو الاحتمال الدقيق لكون ثلاثة أعداد أولية فقط ثابتة، بينما الاثنان والعشرون الباقون "foolish". الحلول البرمجية تحسب هذه الصيغة المعيارية مباشرة بدل تكوين عدد صحيح ضخم ثم قسمته لاحقًا على \(100!\).
داخل المجموع المتناوب، لا تعيد البرامج حساب العوامل والمركبات من الصفر في كل مرة، بل تستعمل الحد المعياري
$$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$$
بحيث يصبح
$$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$$
أما الحد الأول فهو
$$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$$
والحدود المتجاورة تحقق العلاقة
$$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$$
وهذه العلاقة هي بالضبط ما تُحدِّثه تطبيقات C++ وPython وJava داخل الحلقة الرئيسية. ميزتها أنها تتجنب إنشاء قيم وسطية هائلة من العوامل ثم التخلص منها مباشرة بالقسمة.
لنأخذ مثالًا أصغر يوضح نفس الفكرة. افترض أن \(n=8\) و\(m=3\) ونريد بالضبط \(f=1\) عنصرًا معلَّمًا ثابتًا. عندئذ يكون \(b=2\). أولًا نختار العنصر المعلَّم الثابت بعدد
$$\binom{3}{1}=3$$
طرق. بعد ذلك يبقى \(7\) عناصر، ويجب على العنصرين المعلَّمين الآخرين ألا يعودا إلى موضعيهما. يعطي الشمول والاستبعاد
$$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$$
وبما أن \(8!=40320\)، فالاحتمال يساوي
$$\frac{11160}{40320}=\frac{31}{112}.$$
Problem 239 هو التطبيق نفسه تمامًا ولكن على \(100\) عنصر و\(25\) عددًا أوليًا و\(3\) نقاط تثبيت أولية مسموحة و\(22\) نقطة تثبيت أولية ممنوعة.
تبدأ الحلول من المعلمات العامة: العدد الكلي \(n\)، وعدد العناصر المعلَّمة \(m\)، وعدد العناصر المعلَّمة المطلوب أن تكون في غير مواضعها. ومن ذلك تستنتج \(f=m-r\)، أي عدد نقاط التثبيت المعلَّمة. وفي Problem 239 تتحول عبارة "22 foolish primes" بهذه الخطوة إلى "3 نقاط تثبيت أولية".
بعد ذلك تحسب \(\binom{m}{f}\) بطريقة ضربية. أما المجموع المتناوب فيُقيَّم من خلال صيغة \(T_j\): يُبنى \(T_0\) أولًا بقسمة متتالية على \(n\) ثم \(n-1\) وهكذا لعدد \(f\) من العوامل، ثم يُستخرج كل حد جديد من الحد السابق بضربه في النسبة الكسرية المذكورة أعلاه. بهذه الصورة يترجم التنفيذ اشتقاق الشمول والاستبعاد مباشرة إلى حساب عددي قصير وواضح.
في النهاية يُضرب المجموع في \(\binom{m}{f}\)، ويُطبع الناتج على صورة عدد عشري من اثنتي عشرة خانة. كما أن تنفيذ C++ يتضمن اختبارات صغيرة للتحقق: فهو يقارن الصيغة بعدٍّ دقيق وباستعراض كامل على أمثلة صغيرة، ويتأكد في مثال اختباري من أن مجموع الاحتمالات عبر كل قيم \(f\) الممكنة يساوي \(1\).
حساب \(\binom{m}{f}\) يحتاج إلى \(O(\min(f,m-f))\) خطوة حسابية، والمجموع المتناوب يحتوي على \(b+1=m-f+1\) حدًا فقط. لذلك يكون الزمن الكلي \(O(m)\)، بينما تبقى الذاكرة الإضافية \(O(1)\).
وفي المثال الفعلي للمسألة يكون ذلك صغيرًا جدًا: لدينا \(f=3\) و\(b=22\)، أي إن الحلقة الرئيسية تجمع \(23\) حدًا فقط. الصعوبة الحقيقية هنا في بناء العد التوافقي الصحيح، لا في كلفة التنفيذ.