from sympy import *
import random
import matplotlib.pyplot as plt

x, y, z, a, b, c = var('x y z, a, b, c')

1. 排队接水

def cost(times):
    wait_t, tot_t = 0, 0
    for t in times:
        tot_t += wait_t
        wait_t += t
    return tot_t / len(times)

cost([a, b, c])

$\displaystyle \frac{2 a}{3} + \frac{b}{3}$

我们在什么情况下能通过交换 $a \to b$ 到 $b \to a$，改变总的打水时间？

cons = cost([x, y, a, b, c]) > cost([x, y, b, a, c])
cons

$\displaystyle \frac{2 a}{5} + \frac{b}{5} + \frac{4 x}{5} + \frac{3 y}{5} > \frac{a}{5} + \frac{2 b}{5} + \frac{4 x}{5} + \frac{3 y}{5}$

让我们化简它！

simplify(cons)

$\displaystyle a > b$

我们也可以尝试 “交换” 不相邻的两个同学：

simplify(cost([a, b, c, x, y]) > cost([a, x, c, b, y]))

$\displaystyle b > x$

更有趣的是，我们可以尝试 “交换” 不止两个同学，例如以下是满足 “反序” 能使总代价最小的条件：

simplify(cost([a, b, c, x, y]) > cost([y, x, c, b, a]))

$\displaystyle 2 a > - b + x + 2 y$

2. 拼数与排序

Verification (证明) v.s. Validation (测试)：先直觉，再找证明。

fragments = [
    '1', '2', '7', '8', '9', '88', '99', '888', '999'
]

def gen(n):
    return ''.join(
        random.choice(fragments) for _ in range(n)
    )

def less(a, b):
    return a + b < b + a

def check_reflexive(a):
    assert not less(a, a)

def check_antisymmetric(a, b):
    if a + b != b + a:
        assert less(a, b) or less(b, a)

def check_transitive(a, b, c):
    if less(a, b) and less(b, c):
        assert less(a, c)

for i in range(100000):
    a = gen(random.randint(3, 5))
    b = gen(random.randint(3, 5))
    c = gen(random.randint(3, 5))
    check_reflexive(a)
    check_reflexive(b)
    check_reflexive(c)
    check_antisymmetric(a, b)
    check_antisymmetric(a, c)
    check_antisymmetric(b, c)
    check_transitive(a, b, c)

print('Checked')

Checked

3. 区间与选择

和之前的例子不同

# ---------- GPT-4-turbo 生成的代码 (绘图 & 生成) ----------

def plot_intervals(intervals):
    _, ax = plt.subplots(figsize=(6,2))
    y, ymax = 0, 0  # Initial y position
    plotted_intervals = []  # Keep track of plotted intervals to handle overlaps
    
    ax.set_xticks([])
    ax.set_yticks([])

    for interval in intervals:
        # Check for overlap and adjust y if necessary
        overlap = True
        while overlap:
            overlap = False
            for pi in plotted_intervals:
                if not (interval[1] <= pi[0] or interval[0] >= pi[1]) and pi[2] == y:
                    y += 0.25  # Move up if there's an overlap
                    ymax = max(y, ymax)
                    overlap = True
                    break
        
        # Plot the interval
        ax.plot(interval, [y, y], marker='|', markersize=15)
        plotted_intervals.append((interval[0], interval[1], y))
        
        # Reset y if it was adjusted, for the next interval
        if y != 0:
            y = 0
    
    # Set limits and labels
    ax.set_ylim(-0.25, ymax + 0.25)  # Adjust y limits to fit all intervals
    plt.show()

def generate_intervals(n):
    def generate_helper(numbers):
        if not numbers:
            return [[]]
        intervals = []
        # We skip the first number for the end point because an interval
        # cannot have the same start and end point.
        for i in range(1, len(numbers)):
            # Choose the current number as the start point and numbers[i] as the end point
            start, end = numbers[0], numbers[i]
            # Generate all combinations for the remaining numbers
            for rest in generate_helper(numbers[1:i] + numbers[i+1:]):
                intervals.append([(start, end)] + rest)
        return intervals

    # Start with a list of numbers from 1 to 2n
    numbers = list(range(1, 2 * n + 1))
    n = 0
    for intervals in generate_helper(numbers):
        n += 1
        plot_intervals(intervals)
    print(f'{n} configurations generated.')

# ---------- GPT 生成的代码结束 ----------

generate_intervals(2)

3 configurations generated.

generate_intervals(3)

15 configurations generated.

4. 不显然的结论和更多的推导

这次，我们就不借助程序了，这个问题看起来就像是人为 “构造” 出来的。