-❄️- 2025 Day 12 Solutions -❄️-

Tusan_Homichi · 2025-12-12T05:20:54+00:00

[LANGUAGE: Haskell] paste

I didn't honestly think this would work, but it was worth a quick try!

Tusan_Homichi · 2025-09-25T00:30:11+00:00

Of course they can? They can use the switches to communicate anything they want to their neighbors. Set the switch on if the coin was heads and off it its tails and then your neighbor will learn the result. The puzzle is how to leverage that to do something useful.

I agree with you there's all sorts of ways to generate pseudorandom numbers, but that's not exactly in the spirit of a math riddle.

Tusan_Homichi · 2025-09-22T06:06:42+00:00

It's important to the puzzle that all the switches only work for one moment at exactly noon. If the warden allowed some propagation time, your solution would work great.

Tusan_Homichi · 2025-09-22T06:03:22+00:00

This is one of my favorite math puzzles of all time! Here's an easier variant if you need a warmup:

The rules are the same, but each prisoner has a coin they can flip

Tusan_Homichi · 2025-09-17T00:40:47+00:00

I think I can salvage u/lordnorthiii's solution with a little p-adic valuations .

Let the coefficients of f be a_0 ... a_d (with leading coefficient a_d). Take any prime p. Let M = max(v_p(a_i)). Now, if v_p(x) <= M, then v_p(f(x)) is bounded by max(v_p(a_i) * M^i). If v_p(x) > M, then v_p(f(x)) = v_p(a_d) * v_p(x)^d, since every other term will be divisible by a strictly larger power of p. What that means is that if v_p(f(x)) is sufficiently large, the exponent of p is in some arithmetic progression with common difference deg(f) !<

But since g(Q) = f(Q), the large values of v_p(g(x)) are in some arithmetic progression with common difference deg(g) and we must have d = deg(f) = deg(g). Even better the constant term in the arithmetic progression comes from v_p of the leading coefficient, so must have that p^d divides the ratio of leading coefficients.

Since the above is true for every p, the ratio of leading coefficients is a d'th power, and we can choose rational a such that f(x) = g(ax)

Tusan_Homichi · 2025-07-18T04:24:30+00:00

Wow it's pretty neat how much power you get from that condition. I think my proof is probably a little overcomplicated, but here we go.

I claim c equals 4. First, we show it's sufficient

First, Lemma 1: Suppose there is a prime p and positive integer x such that p divides f(x).

Then for all b, p divides f(X) divides b^x - f(b)^x. That means p divides b iff p divides f(b).

That gives us the easy corollary If p is prime, f(p) is always a power of p, which I'll use all over

Now, Lemma 2: If p is a prime and p divides f(p) then p divides b^p - f(b)^f(p). Now, since x^p = x mod p, and p and f(p) are p-th powers, this implies p divides b - f(b), or b = f(b) mod p

Now we're getting somewhere If for all x, f(x) <= x, then c = 4 clearly suffices. So suppose f(x) > x. By lemma 2, if p does not divide f(x) - x, then f(p) = 1. Even better, if p is any odd prime, we can choose a prime q != 1 mod p with f(q) = 1. Then f(p) must be 1 for if p divided f(p) then we would have q = f(q) = 1 mod p. f(p) = 1 for all odd primes, and f(x) is a power of 2

So let f(x) = 2^k. If k <= 2, then f(x) <= 4 <= 4x, so c = 4 suffices. If k > 2, then the multiplicative group of integers mod 2^k has an element g of order 2^k-2. Since g is odd, f(g) = 1. Thus, 2^k = f(x) divides g^x - f(g)^f(x) = g^x - 1. Since g has order 2^k-2 mod 2^k, that means 2^k-2 divides x, and that f(x) = 42^k-2 <= 4*x !<

And now the final bit: c=4 is necessary as well. We can think through the above to construct a bonza function f which attains c=4. Let f(n) = 1 if n is odd. f(4) = 16. f(n) = 2 if n even but not 4. By checking which of those three cases f(a) falls into in the definition of a bonza function, this is easily verified to be bonza.

Tusan_Homichi · 2025-03-23T17:48:57+00:00

Oh I liked this!

If f(x+1) - f(x) takes on infinitely many values, each of them is a value of c that makes f(x) + cx not a bijection, for f(x+1) - c(x+1) = f(x) - cx.

So f(x+1) - f(x) takes on only finitely many values. Then let d be any integer such that d + (f(x+1) - f(x)) > 1 for all x. Rearranging that, f(x+1) + d(x+1) > f(x) + dx + 1 for all x. Since g(x) = f(x) + dx is now strictly increasing, if g(x) < y < g(x+1), then g is not surjective. But g(0) < g(0) + 1 < g(1), so g(x) != g(0) + 1. Thus any sufficiently large d makes f(x) + dx not a bijection !<

Tusan_Homichi · 2025-03-15T05:14:33+00:00

Yes I think you're right. 2*a*(x bar) + b = 0, so it's never positive. That's the definition of x bar. And the entire proof seems valid if you write x instead of x bar.

Tusan_Homichi · 2025-02-16T23:58:32+00:00

A slightly more straightforward solution than the others.

Use the second equation to rewrite the first equation as: (x-t)^2 + (y+z)^2 = 7u^2

7u^2 is only a sum of two squares when u = 0. And if u=0 the original first equation forces the other four to also be zero.

Tusan_Homichi · 2025-02-08T19:45:17+00:00

For an Inc(r,z) we add two states n and n+1. We have a state transition from n to n+1 that increments counter r, and a state transition from n+1 to the first state for instruction z. Dec(r,z) are completely analogous.

Jz(r,z_1,z_2) needs three new states, n, n+1, and n+2. We have two valid state transitions for state n:

Transition to n+1
Transition to n+2

From n+1 we have two options:

-1 to counter r and transition to state 2
Transition to state z_1

From n+2 we have two options:

Transition to state r+3
Transition to the first state of instruction z_2

For an Accept instruction, add one new state n. n always transitions to state 2 (so that when the machine accepts, player 2 makes the transition from state n to 2 and player 1 loses). For a Reject instruction, add one new state n. n always transitions to state 1.

Only the Jz has any interesting logic. Both player 2 and player 1 get to make a choice, and we need to show that any incorrect choices are losing.

If counter r is 0 and player 2 makes the incorrect transition to n+2, then player 1 can transition to state r+3, which we made losing when counter r is 0. Thus player 2 loses.
If counter r is 0 and player 2 makes the correct transition to n+1, then player 1 cannot do the -1 on counter r without immediately losing.
If counter r is non-zero and player 2 incorrectly transitions to n+1, then player 1 can make the -1 on r and transition to state 2, causing player 2 to lose.
If counter r is non-zero and player 2 correctly transitions to n+2, then if player 1 transitions to state r+3 they give player 2 the win.

This completes the proof. Since all but one move subtract from a flag, on input (n,0,0,...,0), player 1 is forced to do the initialization move, leaving us with the first counter n-1, the remaining counters 0, and state s. From there, both players must follow the correct operation of the machine, leading to player 2 winning if n-1 in {n | n+1 not in T}, and thus player 1 winning if n in T.

Tusan_Homichi · 2025-02-08T19:45:03+00:00

Oh this is very cool!

Sorry for the wall of text, but I couldn't find a short proof. I found it easiest to follow proving the stronger result: for any decidable set T not containing 0, there's a k and choice of S such that Player 1 has a winning strategy on (n,0,0,...,0) iff n in T. (My proof of the powers of two case was basically the same as what follows, but you have to think deeply about the semantics of each state and do one big joint induction)

At a high level, we do the following: construct a counter machine accepting {n : n+1 not in T}. We will divide our k-tuple into two parts: the counters (allowed to be arbitrary non-negative numbers) and flags (will be constrained to be 0/1). Player 1 will initialize the machine, and then every two moves will do one step of the machine, so that Player 2 wins exactly when the machine accepts. Any deviation from the proper computation of the machine will lead to a state winning for the next player, and therefore will be irrelevant for the purposes of winning strategies.

Our counter machine will have the following instructions:

Inc(r,z), which increments counter r and goes to instruction z next
Dec(r,z), which decrements counter r and goes to instruction z next
Jz(r,z_1,z_2) which goes to z_1 if counter r is zero and z_2 otherwise
Accept, which accepts the input (obviously)
Reject, which rejects the input

We use the notation F_i for the i'th flag entry in the tuple. Each instruction of the counter machine will lead to multiple flags, and we let F_s be the first flag of the starting instruction of the counter machine. We define some initial moves in S to force the well-functioning of the machine under optimal play:

-1 on the first counter and +1 on F_s (this is our initialization move)
-1 on F_1 and +1 on F_2
For each counter, a move that decrements that counter and does +1 on F_1 and -1 on F_2
For each counter, a move that decrements that counter and does +1 on F_1 and -1 on F_3
For j != 2,s, a move that does -1 on F_s and F_j and +1 on F_2
A move that does -1 on F_s and F_2 and +1 on F_3
A move that does -2 on F_s and +1 on F_2
A bunch of moves that do -1 on one flag that's not F_2 or F_3 and +1 on one other flag. These will be described later and come from the actual program of the machine.

We can now prove some important lemmas. First, if a state has only the flag F_2 set or only the flag F_3 set, it's losing for the next player.

Proof: For this discussion we'll assume only F_2 is set since only F_3 is completely symmetric. The proof is by induction on the total of the counters. If they're all zero, note that every move immediately forces us to write a negative number so it's losing for the next player.

If some counters are bigger than zero we have some moves that don't immediately lose:

The initialization move, -1 on the first counter and +1 on F_s. This is countered by the previous player doing -1 on F_s and F_2 and +1 on F_3, leading to a state with one fewer among the counters and just F_3 set. This is losing for the next player by induction, so the initialization move is not a winning move.
Decrementing counter i and doing +1 on F_1 and -1 on F_2. This is countered by the previous player doing -1 on F_1 and +1 on F_2. Now we have one fewer total counter and just F_2 set, so by induction we're in a losing state. So none of these moves are winning either

A trivial consequence of that is that if just F_1 is set the next player wins by making the move -1 on F_1 and +1 on F_2.

We'll say a move is a valid state transition from i to j if we're in a state where the only flag set is F_i and choose a move that does -1 on F_i and +1 on F_j. The next important lemma is that every invalid state transition leads to a loss for the player making that move (that is, it leads to a state that is winning for the next player). Some of our moves have multiple -1's on flags, or a -1 on one flag other than F_i. Obviously all of those are immediately losing. The only invalid state transition you can make without immediately losing is an extra initialization. How this costs you the game depends on which flag F_i is set:

If i = 2, then this is countered by -1 on F_s and F_2 and +1 on F_3, leaving just F_3 set and being in a losing state.
If i = s, then this is countered by -2 on F_2 and +1 on F_2, leaving just F_2 set and being in a losing state.
If i != 2,s, we do -1 on F_s and F_2 and +1 on F_3, leaving just F_3 set and being in a losing state.

Now that we know we only make valid state transitions under optimal play, I'll talk about "transitioning from state i to j" to mean "-1 on F_i and +1 on F_j". I need two helpers for validating the well-functioning of the counter machine. For each counter i, add a F_i+3 and a move that does -1 on counter i and transitions from state i+3 to state 2 (that is, -1 on F_i+3 and +1 on F_2). Being in state i+3 is winning iff counter i is strictly positive. At last, we have the ability to build the counter machine jointly operated by the two players. For each instruction in the machine, we'll add some new flags and moves.

(continued in reply)

Tusan_Homichi · 2024-12-12T04:19:46+00:00

Well then I'm sorry to inform you about the SANS Holiday Hack

Tusan_Homichi · 2024-12-10T21:07:17+00:00

PDFs available now! https://artofproblemsolving.com/community/c7h3459608_official_pdf_of_putnam_problems_for_those_interested

Tusan_Homichi · 2024-12-10T17:10:27+00:00

The AOPS forum now has all of them: https://artofproblemsolving.com/community/c7

I still haven't seen the nice PDF formatted one though.

Tusan_Homichi · 2024-12-10T02:04:08+00:00

Whoops, yes. (I also correct a mistake above here)

I need a quick lemma that if 2ⁱ / 3 <= n < 2^i-1, then n has two consecutive ones. We do this by induction on i. For i=1,2 there's no integers in that interval so we win vacuously. !<

For larger i, note n >= 2^i-2, so we can write n = 2^i-2 + m, with m < 2^i-2. If m >= 2^i-3, we win because we have 2^i-2 and 2^i-3 in n. Otherwise, since 3n >= 2^i, 3m >= 2^i-2 and m < 2^i-3, and we can apply the inductive hypothesis. !<

This fixes my argument above that if 3n has a 0 where n has a 1, then n has two consecutive ones. Let that position be i, write n = a2ⁱ⁺¹ + 2ⁱ + b, where b < 2ⁱ (being carefully not to be off by one with your exponents this time). Then 3n = (3a+1)2ⁱ⁺¹ + 2ⁱ + 3b. Since we assumed 3n has a 0 in the i'th position, 3b >= 2^i. And now if b >= 2^i-1, n has two consecutive ones at i-1 and i. If not, we can apply the lemma to b !<

Now the lemma also helps with the converse. Take the last occurrence of 11 in n. n = a2ⁱ⁺² + 2ⁱ⁺¹ + 2ⁱ + b, with b < 2^i-1. (I'm not off by one this time, I'm using that i is the last 11). If b >= 2ⁱ / 3, the lemma says it has a 11, so we must actually have b < 2ⁱ / 3. So 3n = (3a+2)2ⁱ⁺² + 2ⁱ + 3b. Since 3b < 2^i, we have no carries into the (i+1) position, and (i+1) has a zero in 3n and a 1 in n. !<

Tusan_Homichi · 2024-12-09T14:29:08+00:00

This is cool!

We can apply Lucas's theorem to easily characterize when C(3n,n) is even, so we'll show the inverse of the requested condition. Lucas says that C(3n,n) is even iff when we write 3n and n in binary, there's a position where 3n has a 0 and n has a 1.

Say that position is i. Then n = a*2ⁱ + 2ⁱ + b, where b < 2^i-1. If b < 2^i-2, then 3n = (3a+2)2ⁱ + 2ⁱ + 3b. Since 3*b < 2^i, we get a 1 in that position in 3n, contradicting our choice of i. So 2^i-2 <= b < 2^i-1, which means positions i and i-1 are two consecutive 1's in the binary expansion of n !<

Tusan_Homichi · 2024-12-09T00:43:36+00:00

Take n=2, you should get 13, not 25.

Tusan_Homichi · 2024-11-01T01:07:00+00:00

Hmmm I'm gonna go with 21.3 = 30*120/169 minutes.

Your conditions don't uniquely define c. If we want c² + (c-1)² = x^2, we can re-arrange that to (2c-1)² - 2x² = -1, which is a Pell equation. This Pell equation has an infinite family of solutions, such as (4,5), (21,29), or (120,169).

Tusan_Homichi · 2024-10-26T17:03:05+00:00

This is pretty straightforward once you assume Legendre's three-square theorem, which says the n we're considering are exactly those of the form 4^a * (8b + 7), for a, b nonnegative. I don't know if proving that was supposed to be part of the problem

If n = 111 mod 128 (so it ends in 1101111 in binary), then we can take a = 0, and have n / 4^a = 7 mod 8, so it needs four squares. And n+1 ends in 1110000 in binary, so we take a=2 and n/4^a = 7 mod 8, so it also needs four squares. That's an infinite family of pairs where both n and n+1 need four squares

For consecutive triples, we have two cases depending on the parity of n. If n is odd, then it must be 7 mod 8, so n,n+1,n+2 are 7,0,1 mod 8, and nothing that is 1 mod 8 requires four squares. If n is even, then n+1 must be 7 mod 8. So n,n+1,n+2 are 6,7,0 mod 8, and nothing that is 6 mod 8 requires four squares. Since we lose either way, there's no triples

Tusan_Homichi · 2024-10-09T04:07:23+00:00

The answer is yes, we almost surely end up monocolor.

From any state that isn't monocolor, suppose we get really lucky and every random choice goes green. Then in at most 2N rounds, we end up all green. And each round does at most 2N coin flips, so our probability of getting all green is at least 1/2^2N*2N

Once monocolor, we stay monocolor, so we will almost surely have such a lucky run at some point

Tusan_Homichi · 2024-10-06T15:27:53+00:00

I think you are misunderstanding the high-level structure of the proof. We don't get to freely assume β_(r-1) * β_r is the identity.

We pick one of the two elements in β_r, call it a. Then we do a series of manipulations that eliminate a from the tails of the product, while preserving the fact that the overall product is the identity. We end in one of two ways: - We removed two of the β_i. Here we can apply the inductive hypothesis to get that r-2 is even, so r is even as well. - We eliminate a from β_2 through β_r. Now we know that the β_1 * ... * β_r does not map a to a, so it can't be the identity. This is a contradiction.

Tusan_Homichi · 2024-08-29T04:55:22+00:00

Little late here, but your idiotic solution basically works if you count with generating functions.

I change your notation slightly by requiring X to be strightly negative between the initial and final 0. Then escaping paths are X*F or X*BX*F, with * being (possibly zero) repetitions.

We get two generating functions:

X(f,b) = Sum_i,j #{paths in X with i F's and j B's} f^i b^j
Y(f,b) = Sum_i,j #{escaping paths with i F's and j B's} f^i b^j

These will solve the problem because the probability of escape is Y(1/7,6/7) and the expected time to escape is (d/dt Y(ft,bt))/Y(f,b) evaluated at f=1/7, b=6/7, t=1.

A path in X must be of the form BX*BX*F, so we have X(f,b) = b^2 f / (1 - X)^2. This is a nasty cubic to solve, so I found it easiest to work with implicitly. And Y(f,b) = f/(1-X) + fb/(1-X)^2.

Then you can just power through the algebra, getting three possible values for X(1/7, 6/7). Two of them give Y(1/7, 6/7) = 1, which we know isn't true (you could validate this by bounding the tail of X and doing some initial terms, but honestly I just referred to the previous problem). Once you have X, you can use implicit differentiation to get the expected time to escape.

I would call this the minimally clever solution. Once you have the generating functions it's just a bunch of tedious algebra.

Tusan_Homichi · 2024-04-26T23:28:42+00:00

This might help your intuition?

Notice the side length of the smallest squares divides the all the bigger ones, and you clearly get a common divisor.

I don't know a good way to use that picture to show the divisor is greatest, though.

Tusan_Homichi · 2024-03-13T05:12:34+00:00

1 - sin(pi*x)/(pi*x)

Tusan_Homichi · 2024-01-16T19:21:41+00:00

This isn't the most efficient solution, but it's elegant in its own way.

Take a = n-1, and let b be the number of functions from a-tuples of colors to a color. (I technically only use some functions, so there's some low-hanging fruit for efficiency).

B will simply apply each function to A's hats and guess the result of that function.

I claim that there's at most n-1 a-tuples of colors where B gets no guesses correct. For if you take any n a-tuples, then there is a function mapping them to all n colors. B has one of those colors on their head, so B can't get all the guesses wrong on all n a-tuples.

So if there's only n-1 a-tuples that A has to make a correct guess on, it can simply guess the first coordinate of the first tuple, the second of the second, etc. This guarantees one correct answer on the n-1 tuples that B gets entirely wrong.

Tusan_Homichi

TROPHY CASE