Problem #100 medium

Arranged probability

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, $P(\text{BB}) = (15/21) \times (14/20) = 1/2$ .

The next such arrangement, for which there is exactly $50\%$ chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over $10^{12} = 1\,000\,000\,000\,000$ discs in total, determine the number of blue discs that the box would contain.

View on Project Euler

Implementations

#include <iostream>
#include <cmath>

long long arranged_probability() {
    // Use the recurrence for solutions to 2b(b-1) = n(n-1)
    // Find the smallest b where n > 10^12
    long long b = 15, n = 21;
    while (n <= 1000000000000LL) {
        long long b_new = 3 * b + 2 * n - 2;
        long long n_new = 4 * b + 3 * n - 3;
        b = b_new;
        n = n_new;
    }
    return b;
}

View on GitHub

~1ms

package main

func arrangedProbability() int64 {
    b, n := int64(15), int64(21)
    for n <= 1000000000000 {
        b_new := 3*b + 2*n - 2
        n_new := 4*b + 3*n - 3
        b = b_new
        n = n_new
    }
    return b
}

View on GitHub

~1ms

public class Euler100 {
    static long arrangedProbability() {
        long b = 15, n = 21;
        while (n <= 1000000000000L) {
            long b_new = 3 * b + 2 * n - 2;
            long n_new = 4 * b + 3 * n - 3;
            b = b_new;
            n = n_new;
        }
        return b;
    }
}

View on GitHub

~1ms

function arranged_probability() {
  let b = 15n, n = 21n;
  const limit = 1000000000000n;
  while (n <= limit) {
    const b_new = 3n * b + 2n * n - 2n;
    const n_new = 4n * b + 3n * n - 3n;
    b = b_new;
    n = n_new;
  }
  return Number(b);
}

View on GitHub

~1ms

def solve():
    b, n = 15, 21
    while n <= 10**12:
        b_new = 3 * b + 2 * n - 2
        n_new = 4 * b + 3 * n - 3
        b, n = b_new, n_new
    return b

View on GitHub

~1ms

pub fn arranged_probability() -> i64 {
    let mut b: i64 = 15;
    let mut n: i64 = 21;
    while n <= 1_000_000_000_000 {
        let b_new = 3 * b + 2 * n - 2;
        let n_new = 4 * b + 3 * n - 3;
        b = b_new;
        n = n_new;
    }
    b
}

View on GitHub

~1ms

#include <iostream>
#include <cmath>

long long arranged_probability() {
    // Use the recurrence for solutions to 2b(b-1) = n(n-1)
    // Find the smallest b where n > 10^12
    long long b = 15, n = 21;
    while (n <= 1000000000000LL) {
        long long b_new = 3 * b + 2 * n - 2;
        long long n_new = 4 * b + 3 * n - 3;
        b = b_new;
        n = n_new;
    }
    return b;
}

View on GitHub

~1ms

package main

func arrangedProbability() int64 {
    b, n := int64(15), int64(21)
    for n <= 1000000000000 {
        b_new := 3*b + 2*n - 2
        n_new := 4*b + 3*n - 3
        b = b_new
        n = n_new
    }
    return b
}

View on GitHub

~1ms

public class Euler100 {
    static long arrangedProbability() {
        long b = 15, n = 21;
        while (n <= 1000000000000L) {
            long b_new = 3 * b + 2 * n - 2;
            long n_new = 4 * b + 3 * n - 3;
            b = b_new;
            n = n_new;
        }
        return b;
    }
}

View on GitHub

~1ms

function arranged_probability() {
  let b = 15n, n = 21n;
  const limit = 1000000000000n;
  while (n <= limit) {
    const b_new = 3n * b + 2n * n - 2n;
    const n_new = 4n * b + 3n * n - 3n;
    b = b_new;
    n = n_new;
  }
  return Number(b);
}

View on GitHub

~1ms

def solve():
    b, n = 15, 21
    while n <= 10**12:
        b_new = 3 * b + 2 * n - 2
        n_new = 4 * b + 3 * n - 3
        b, n = b_new, n_new
    return b

View on GitHub

~1ms

pub fn arranged_probability() -> i64 {
    let mut b: i64 = 15;
    let mut n: i64 = 21;
    while n <= 1_000_000_000_000 {
        let b_new = 3 * b + 2 * n - 2;
        let n_new = 4 * b + 3 * n - 3;
        b = b_new;
        n = n_new;
    }
    b
}

View on GitHub

~1ms

Solution Notes

Mathematical Background

The problem requires finding integer solutions to b(b-1)/(n(n-1)) = 1/2, which simplifies to 2b(b-1) = n(n-1). This Pell-like equation has solutions generated by a recurrence relation.

Algorithm Analysis

Start from known small solution (b=15, n=21) and iterate the recurrence b_new = 3b + 2n - 2, n_new = 4b + 3n - 3 until n > 10^12.

Performance

Extremely fast (~1ms) due to simple arithmetic operations and few iterations.

Key Insights

Pell equation solutions follow linear recurrence
Direct computation without solving quadratic each time

Educational Value

Demonstrates Pell equations, recurrence relations, and efficient generation of integer solutions to Diophantine equations.

Jump to problem:

All Problems / Problem 100

← Problem #99 Largest exponential

Problem #100 is taken from Project Euler and licensed under CC BY-NC-SA 4.0.