Flip Coins: Compute the Expected Number of Heads After Applying a Sequence of Flip Operations

Question

## Problem

You start with `n` coins all showing tails (0). You perform `k` operations. Each operation `i` flips every coin at positions that are multiples of `i` (1-indexed). After all operations, how many coins show heads?

```python
def count_heads(n: int, k: int) -> int:
    pass
```

**Example:**
```
n=6, k=3
# Op 1: flip multiples of 1 -> [H,H,H,H,H,H]
# Op 2: flip multiples of 2 -> [H,T,H,T,H,T]
# Op 3: flip multiples of 3 -> [H,T,T,T,H,H]
output -> 3
```

## Follow-ups
1. For `k >= n`, a coin at position `p` is flipped by every divisor of `p` up to `k`. Can you derive a closed-form count without simulating?
2. A coin ends heads if it is flipped an odd number of times. Which numbers have an odd number of divisors? (Perfect squares -- use this insight.)
3. Extend: each operation has a probability `p_i` of actually executing. Compute the expected number of heads.
4. What if flipping is toggling between 3 states (tails, heads, edge) instead of 2?

Flip Coins: Compute the Expected Number of Heads After Applying a Sequence of Flip Operations

Question Details

Full Details

Topics

More from Square/Block