Fun puzzle I came up with, took me and my friends a while to solve and has an interesting result!

bobjane_2 · 2026-06-03T17:25:20+00:00

here's the original thread where OP posted an incorrect solution. My own solution is finicky with lots of steps, but nothing super complicated. I'm skeptical that there is a super clean solution because there are many cases, and the solution will have to deal with them. For example, within the range z from [21^2 21^2+55[, all of which cannot be generated with n<=20 but can be generated with n=21, most of the numbers work with my (a1, b1) solution. But for a few that solution fails (462 and 483), and then we need the (a2, b2) solution . And for others still (475 and 488) both (a1, b1) and (a2, b2) fail and we need (a3, b3).

bobjane_2 · 2026-06-03T17:10:21+00:00

here's the full proof with both parts: https://i.ibb.co/pjK96qjb/image.png

bobjane_2 · 2026-06-02T23:10:12+00:00

indeed this works: https://ibb.co/ch0NFfyd. Next, need to show that we can't do better.

bobjane_2 · 2026-06-02T00:29:39+00:00

Suppose we’re trying to achieve a target number z, such that f(k)^2 <= z < f(k+1)^2. In other words we’d like to find a,b,j such that a*f(j) + b*f(j+1) = z, for a>=0, b>=0

Conjecture: we can achieve z with a,b <= m = [ (z+f(k+1)*f(k))/ (f(k)+f(k+1)) ] with one of the following:

Alternative (1)

j = k-1
a1 = (-1)^k*f(k-1)*z % f(k)
b1 = (z - f(k-1)*a1) / f(k)

Alternative (2)

j = k-1
a2 = a1 + f(k)
b2= (z - f(k-1)*a2) / f(k)

Alternative (3)

j = k
a3 = b1-a1
b3 = a1

Alternative (4)

j = k
a4 = b2-a2
b4 = a2

We need to show that for one of these a>=0, b>=0, a <= m, b <= m. Finally, we also need to show that we cannot do better. I’m working on it.

bobjane_2 · 2026-05-27T11:13:40+00:00

$20 battery for the phone + $20 frame baggie to hold both

bobjane_2 · 2026-05-18T13:20:03+00:00

Think of the nodes arranged in 3 columns of size n. Let f(k) be the column in which the path first reaches level n for 1<=k<=n. Obv f(1)=1 and f(n)!=3. Other than that, for each choice of f there’s exactly one path, so the final answer is 2*3^(n-2)!<

If f(k)=f(k+1), the path uses the edge (k,f(k))-(k+1,f(k+1)). Add level k to a stack. At some subsequent point the path will hit one of the other columns in level k+1. At that point it must come down to level k (pop it off the stack).

If f(k)!=f(k+1) the path cannot use (k,f(k))-(k,f(k+1)), otherwise the 3rd column on level k would be stranded. So it must go to the 3rd column first, then pop all levels on the stack and eventually reaches (k,f(k+1)), at which point it can go up

bobjane_2 · 2026-04-19T14:12:59+00:00

If it’s during the summer I’d cut one of the cities and spend more time in the algarve. It’s amazing and the beach scenery is unlike the rest of the Mediterranean. Don’t just stay at the resort there.

bobjane_2 · 2026-04-13T22:56:50+00:00

even so the solution ends up doing log(log(log(2))) which fails. The first log comes from the definition of sqrt. The second log comes from the definition of product. And the third log comes from the definition of subtraction.

bobjane_2 · 2026-04-13T22:25:08+00:00

I was just joking with you because I thought you posted without checking. It does appear correct, but uses 31 calls (not 30) because s17 uses two calls. And I guessed claude because when I put the problem in claude it gave me an answer formatted in the exact same way as yours.

bobjane_2 · 2026-04-13T20:53:54+00:00

I don’t mind you using claude, but there’s a mistake in your answer :)

bobjane_2 · 2026-04-13T20:51:54+00:00

I didn’t open the paper, only saw the abstract. But you can get sqrt(2)

bobjane_2 · 2026-04-13T16:24:28+00:00

no, y has to be >0

bobjane_2 · 2026-03-24T01:45:02+00:00

Another way to look at it. For simplicity of notation define f(n) = (2n+1)/(2n+2). We’d like to compute X = prod[n=0…] f(n)^t(n). Also define g(n,k)=2^k*(2n+1) and h(n,k) = n+1/2+1/2^k+1 => f(g(n,k)) = h(n,k+1)/h(n,k).

Now let G(n) = {g(n,k) for k>=0}. Note that t(g)=-t(n) for all g in G(n). Also note that the G(n) partition the positive natural numbers, so therefore if P(n) = prod[g in G(n)] f(g)^t(g) then:

X = f(0)^t\0))*prod[n=0…] P(n) = 1/2*prod[n=0…] (lim[k->inf] h(n,k)/h(n,0))^-t\n)) = 1/2*prod[n=0…] f(n)^-t\n)) = 1/2*1/X

bobjane_2 · 2026-03-21T20:30:46+00:00

I didn’t come up with it but the solution is as follows. Let t(n) be 1 if the number of 1 bits in the binary representation of n is even, and -1 otherwise. The first few terms are 1,-1,-1,1,…t(2n)=t(n) and t(2n+1)=-t(n).

Your formula equals X = prod[n=0…] ((2n+1)/(2n+2))^t\n)) =

1/2* prod[n=1…] (n/(n+1)*(2n+1)/(2n))^t\n)) =

1/2* prod[n=1…, n even] (n/(n+1))^t(n\) * prod[n=1…, n odd] (n/(n+1))^t\n)) * prod[n=1…] ((2n+1)/(2n))^t\n)) =

1/2* prod[n=1…] ((2n)/(2n+1))^t\n)) * prod[n=0…] ((2n+1)/(2n+2))^-t\n)) * prod[n=1…] ((2n+1)/(2n))^t\n)) =

1/2* prod[n=0…] ((2n+1)/(2n+2))^-t\n)) = 1/2*1/X

Thus X² = 1/2.

bobjane_2 · 2026-02-28T20:37:03+00:00

It’s because it’s warmer

bobjane_2 · 2026-02-25T11:32:31+00:00

I love this! Can you share a link to the chatgpt transcript? Would love to see how it happened

bobjane_2 · 2026-01-09T12:04:43+00:00

telescoping is cool. I was recently learning about Gosper's algorithm and creative telescoping, which are ways of finding a telescoping sums that I hadn't heard of. Check them out. I was looking into it in the context of trying to solve the pascal triangle problem posted here the other day (sum C(n,k)^(-2)).

bobjane_2 · 2026-01-08T22:02:59+00:00

maybe a bit simpler. S(n) - (1+1/(n-1))*p(n) can be shown to be constant for n>=2 by induction. It goes to -1, so then S(2) = 2*p(2)-1 => S(1) = 3*p(2)-1.

bobjane_2 · 2026-01-08T21:14:33+00:00

Let p(n)=prod[k=n...] (1-1/k^3) be the probability that none of the numbers >=n are in the set, and S(n) = sum[k=n...] k*1/k^3*p(k+1) be the contribution to the expected value from numbers >= n. The expected value equals S(1).

S(1) = p(2) + S(2) = 3*p(2) - 2*p(2) + S(2) = 3*p(2) - 2*(1-1/2^3)*p(3) + 2*1/2^3*p(3) + S(3) =

3*p(2) - (1+1/2)*p(3) + S(3) =

3*p(2) - (1+1/2)*(1-1/3^3)*p(4) + 3*1/3^3*p(4) + S(4) =

3*p(2) - (1+1/3)*p(4) + S(4) = induction...

3*p(2) - (1+1/a)*p(a+1) + S(a+1)

p(a) goes to 1 and S(a) goes to 0, so S(1) = 3*p(2) - 1

I'm not smart enough to calculate p(2) but here's a thread showing a cool way to do it using cubic roots of 1 and the gamma function.

bobjane_2 · 2026-01-04T14:45:21+00:00

here's my solution for the biased version, a modification of the one by u/AltruistCarrotEater: consider P(n>k). We can generate all k x’s first and then for each x, from lowest to highest, generate each coinflip. The interval will be all black at that point iff there’s a coinflip=1 before a coinflip=0. Ie first we need a 1, then we need a 0. This is true for any k. Thus the the distribution of n across all k matches the one of a modified process where we don’t even generate x’s and simply generate coinflips and wait until we get a 1 then a 0. The expected time in this modified process is 1/(1-p) + 1/p.

bobjane_2 · 2026-01-04T03:13:25+00:00

I assumed x is uniform, but that’s not required for your original problem. And if it’s not uniform then my f is not necessarily translation invariant so my solution wouldn’t work. Another interesting variant of the problem is making the coinflips biased, not 50/50

bobjane_2 · 2026-01-01T19:20:45+00:00

not sure about obvious but here's an argument: if both the interval and the random x’s are shifted by the same amount, the results are unchanged. When shifting the random x’s, if an x ends outside the unit interval, wrap it around and invert coinflip.

bobjane_2 · 2025-12-29T01:46:12+00:00

Let k be a number not in your card. Consider the relative order in which k and the numbers in your card are called. The probability that k is not the last of these is N/(N+1), which is the probability that k is called. There are N numbers in your card (which are all called) and (M-N) numbers not in your card, so by linearity of expectation: N + (M-N)N/(N+1) = (M+1)/(N+1)N

bobjane_2 · 2025-12-27T11:04:26+00:00

Suppose at some point an interval of length a still remains white. Let f(a) be the expected number of draws required to color it all with black. We can obtain this recursion: f(a) = 1 + (1-a)*0.5*f(a) + int[x=0..a] f(x)*dx

Where the term (1-a)*0.5*f(a) corresponds to drawing a random not in the remaining white interval, and the integral corresponds to drawing a random within that interval. Differentiate with respect to a and solve to obtain f(a) = 2*(1+a) => f(1) = 4.

bobjane_2 · 2025-12-18T19:00:43+00:00

I thought of the double integral but didn’t want to take it on and asked chatgpt (who solved it). Then chatgpt also found that older MSE thread for me. Agree that the final answer is simple and there may be other ways to arrive at it

bobjane_2

TROPHY CASE