Fibonacci Nim - Play Zeckendorf First?

[@johnchessant3012]

here from Mathemaniac! this is really awesome

[@mostly_mental]

Glad you like it. Thanks for watching!

[@lexinwonderland5741]

Yay! You're back!! I'm always excited to see your videos, friend :) Nim and game-theoretic extensions of number systems (like what Conway and Knuth developed) are truly an underappreciated love of mine. Thank goodness you have Aurora as your assistant!!

[@mostly_mental]

It's good to be back. Game theory is always fun to talk about, and I'm glad there are people who want to hear about it. And yes, Aurora is the best, and I couldn't do it without her.

[@Vierkantswortel2]

Great explanation! Glad you're back!

[@mostly_mental]

Glad you like it. Thanks for watching!

[@pawebielinski4903]

Hello, I'm from Mathemaniac, gonna recommend the channel to my students :)

[@mostly_mental]

I'm glad you like it. Thanks for watching!

[@JulianEpsilon]

9:15 proof If f_n is the highest fib which goes into some number, then [f_(n-1)]+ [f_(n-3)] + [f_(n-5)] ... + [1] is the largest number we can construct without using f_n and following the rules. we can expand each term[f_(n-2) + f_(n-3)]+ [f_(n-4) + f_(n-5)] + [f_(n-6) + f_(n-7)]... + [1 + 0 ] . This sequence is the sum of the first n-2 terms and it sums to f_(n) - 1 . (easy to show via induction.. f_1 + f_2 + f_3 = f_5 - 1, therefore f_1 + f_2 + f_3 + f_4= f_5 + f_4 - 1 = f_6 - 1) So the biggest number we can create without f_n is less than f_n and therefore less than the number we are trying to sum to. This means f_n must be used in our representation. then we can use the same process to deduce that in order to reach (our target - f_n) we must add the largest fib which fits into (our target - f_n). So in order to get a valid representation, we're going to get a single list of numbers we must use, therefore unique.

[@mostly_mental]

Looks right to me. Nicely done.

[@bongo50_]

I found this very interesting and you explained it very clearly. Thanks for making this video.

[@mostly_mental]

Glad you like it. Thanks for watching!

[@purplenanite]

Aurora seems like a good sport!

[@mostly_mental]

She really is the best. She's taught me so much cool math. I'm lucky to have her as my assistant.

[@appybane8481]

13:44 can't you just remove 13?

[@mostly_mental]

If the opponent takes 13, you can immediately remove the remaining 21 and win. The winning play isn't just to take a Fibonacci number, it's to take the smallest Fibonacci number in the Zeckendorf representation.

[@yinq5384]

From Mathemaniac as well. Great video! If we alter the rule from "twice" to "three times", will we be dealing with another sequence?

[@mostly_mental]

Good question. If we modify the code at it 5:39 to use 3 instead of 2, we'll get a related sequence ( oeis.org/A003411 ), where each term a_n is given by a_(n - 1) + a_(n - 4), and all the winning moves seem to belong to that sequence too. And using 4 instead, we get a sequence with a_n = a_(n - 1) + a_(n - 6) ( oeis.org/A003413 ). That suggests there's a nice generalization where a factor of k gives us a sequence with a_n = a_(n - 1) + a_(n - (2k - 2)). There's probably a clever analog of the Zeckendorf representation that gives us a pretty proof, but I don't know it off-hand.

[@yinq5384]

@@mostly_mental Thank you so much! I tried something like a_n = a_(n-1) + 2 a_(n-2) before I posted the comment but it didn't work of course. I never thought of a sequence of high order. Then is it possible to generalize to non-integer case, for example 5/2 or e?

[@mostly_mental]

@@yinq5384 You certainly can. For every ratio I've tried, it looks like you get a sequence with the same sort of behavior (P positions form a sequence, and winning moves from N positions in that same sequence). There almost certainly won't be a nice recurrence relation for every non-integer value. But these sorts of linear recurrence relations are really exponential, so I wouldn't be too surprised if there's a relationship between the chosen ratio and the base of that exponential. If you're interested, this might make for a good research problem.

[@ShalevWen]

I would like to see a video about Chomp

[@mostly_mental]

Excellent suggestion. I'm not sure I know much more than you do (and I'm pretty sure it's still an open problem, so no one else does either), but I'll do some research and see if anyone's published some partial results that could make for an interesting video.

[@lexinwonderland5741]

@@mostly_mental hey, even if you aren't an expert on Chomp, you'd still have the most thorough KZbin education video about it. I encourage you to do it!! (I dont know what Chomp is, either, I just know that I love game theory and especially your videos)