Putting It All Together

This is reservoir sampling. Start with the easy case, k = 1 — keep a single item. The rule: when the i-th item arrives (counting from 1), keep it with probability 1/i, otherwise stick with what you already hold. Why does that give everyone the same 1/n at the end? The last item, number n, is kept with probability 1/n directly. An earlier item j was kept when it arrived (prob 1/j) and then survived every later item not replacing it: (1 − 1/(j+1)) × (1 − 1/(j+2)) × … × (1 − 1/n). Those brackets are j/(j+1) × (j+1)/(j+2) × … × (n−1)/n, a telescoping product that collapses to j/n. Multiply by the 1/j from the start and you get 1/n. Everyone ties.

For general k, keep the first k items as the initial "reservoir". When the i-th item arrives (i > k), keep it with probability k/i; if you keep it, drop one of the k held items chosen at random to make room. The same telescoping argument gives every item a final probability of exactly k/n.

import random

def reservoir(stream, k):
    keep = []
    for i, item in enumerate(stream):     # i counts from 0; n never needed
        if i < k:
            keep.append(item)             # fill the reservoir first
        else:
            j = random.randint(0, i)      # 0..i inclusive → keep with prob k/(i+1)
            if j < k:
                keep[j] = item
                # evict a random held item and insert the new one
    return keep

Answer: reservoir sampling. Hold the first k items; for each later item i keep it with probability k/i, replacing a random current member. It makes one pass, stores only k items, and never needs to know n ahead of time — perfect for a stream too big to hold or of unknown length. A quick simulation (run reservoir many times over range(100) with k = 10 and tally how often each number appears) confirms every element shows up almost exactly k/n of the time.

The core idea is simple: keep three copies of every item, on three well-separated nodes, and never let two items share the exact same trio of nodes. An easy scheme that does this: put item i on nodes i, i+1 and i+2 (wrapping round mod 1000). Every item now has three homes, every node still holds three items, and each item's trio is a distinct set of three consecutive nodes.

An item is lost only when all three of its nodes are down. If just 3 random nodes fail, a given item is lost only if those 3 failures are precisely its 3 nodes. The chance of that for one item is 1 divided by the number of ways to choose 3 nodes from 1000 — that is 1 / C(1000, 3) = 1 / 166 167 000, a tiny number. Add that up over all 1000 items:

expected items lost ≈ 1000 × 1 / C(1000, 3) ≈ 6 × 10⁻⁶

Answer: three copies per item, spread across distinct nodes so no two items share a trio. With 3 random node failures the expected loss is essentially zero — almost always no item is lost at all, and even in the rare case the 3 failures happen to be one item's exact trio, you lose at most about one item. The whole win comes from replication plus spreading the copies out: three copies packed onto overlapping node sets would lose far more.

First the easy half: each merge turns two companies into one, so it reduces the count by exactly one. Going from n down to 1 therefore always takes n − 1 merges, no matter the order. The interesting question is how many ordered ways those merges can play out. Do the small cases by hand:

The closed form that produces 1, 3, 18, … is:

number of merge sequences = n! · (n−1)! / 2ⁿ⁻¹

Check it: n = 2 gives 2 · 1 / 2 = 1; n = 3 gives 6 · 2 / 4 = 3; n = 4 gives 24 · 6 / 8 = 18. All match.

Answer: n − 1 merges are always needed, and the number of distinct ordered merge sequences is n!(n−1)! / 2ⁿ⁻¹, matching the hand counts 1, 3, 18 for n = 2, 3, 4.

Four nested loops would be O(n⁴). Instead use the "remember what you have seen" trick: build every two-cube sum once and look for collisions. Go over each pair (a, b) with a ≤ b < n, and store a³ + b³ in a dictionary keyed by the sum. Any key hit by two or more different pairs is a Ramanujan number.

def ramanujan(n):
    seen = {}                     # sum -> list of (a, b) pairs
    for a in range(1, n):
        for b in range(a, n):     # a <= b avoids double-counting
            seen.setdefault(a**3 + b**3, []).append((a, b))
    return {s: p for s, p in seen.items() if len(p) >= 2}

print(sorted(ramanujan(20)))

The smallest is the famous 1729 = 1³ + 12³ = 9³ + 10³ (the Hardy–Ramanujan taxicab number). One pass over the ≈ n²/2 pairs, O(1) per insert on average.

Answer: hash every a³ + b³ and keep the sums reachable two ways — O(n²) time and space, versus brute-force O(n⁴). Smallest Ramanujan number: 1729.

The trick to every puzzle like this is to reason backwards from the smallest case, because each pirate, when voting, compares "what I get now" against "what I would get if this proposer is thrown overboard". Label the pirates P1 (most junior) up to P6 (most senior); the senior proposes first. "At least half" means a tie is enough to pass.

Part 2-51, dividing $300. Build up one pirate at a time:

Each proposer only has to bribe the cheapest pirates — the ones who would get nothing in the next round — and just enough of them to reach half the votes. So with six pirates, the senior P6 needs 3 votes (his own plus two), and he secures them by handing $1 each to P4 and P2, keeping the other $298 for himself.

Answer (2-51): the top pirate keeps $298 and gives $1 each to two specific juniors (P4 and P2) to secure a passing vote of 3-to-3; P5, P3 and P1 get nothing. Rationality, not generosity, produces the lopsided split — the juniors accept $1 because the alternative is $0.

Part 2-52, a single indivisible dollar. Now the proposer has almost nothing to bribe with, so survival votes do the work. Reasoning down the chain, with 5 pirates the proposer P5 would need 3 votes but can bribe at most one pirate with the lone dollar — so a 5-pirate proposal fails and P5 is thrown overboard. That fact is the key: it means P5 is desperate to avoid ever reaching a 5-pirate game.

So when 6 pirates face the single dollar, the senior P6 needs 3 votes and gets them like this: his own vote; P5's vote for free (because if P6 is thrown over, the game drops to 5 pirates where P5 dies, so P5 will support almost any proposal that keeps P6 afloat); and one more vote bought by giving the single dollar to one of the pirates who would otherwise get nothing (P4, P3 or P1). That is a winning coalition of three, so the proposal passes.

Answer (2-52): the top pirate survives and no one need die. He gives the one dollar to a single pirate whose vote he needs and relies on the vote of P5, who backs him purely to avoid being thrown overboard in the next round. The dollar plus one life-saving vote is exactly enough to form a majority — a neat demonstration that "value survival first" can be worth more than money at the table.

Primary Arithmetic — count the carry operations when two unsigned numbers are added. Add the two numbers the grade-school way, digit by digit from the right, keeping a running carry; each position where the column plus the incoming carry reaches 10 produces a carry into the next column. Count those events. It is O(number of digits), and the whole problem is really just "do primary-school addition and watch the carries" — report none, one, or the count.

A Multiplication Game — two players start from a product of 1 and take turns multiplying it by any integer from 2 to 9; the first to reach or pass n wins, and the first player (Stan) moves first. This is a small combinatorial game: reason backwards from n about which running totals are winning positions for the player about to move. With optimal play the winner depends only on which "band" n falls in, and the band edges are 9, 18, 162, 324, 2916, … — the gaps alternate ×2 then ×9 (not "powers of nine"): Stan wins for n in 2–9, the second player for 10–18, Stan for 19–162, the second player for 163–324, Stan for 325–2916, and so on. A clean rule: repeatedly replace n by ⌈n/18⌉ until n ≤ 18, then Stan wins exactly when the leftover n ≤ 9. No search is needed — just a handful of divisions.

Light, More Light — lamps numbered 1..N start off; person i toggles every lamp whose number is a multiple of i, so lamp k is toggled once for each of its divisors. A lamp ends on exactly when it was toggled an odd number of times, i.e. when k has an odd number of divisors. Divisors come in pairs (d and k/d) except when k is a perfect square (where the square root pairs with itself), so the only lamps left on are the perfect squares. The whole problem collapses to: is k a perfect square? Check with an integer square root in O(1) per query.