grhkm's blog

Math blog topic suggestion
By grhkm, history, 4 years ago, In English

Hello as title, any math topic suggestions that have few resources on, and are not too hard (i.e. it's explainable in one blog, perhaps with high-school maths knowledge)? IMO my previous blogs on maths (lagrange interpolation and linear modulo inversions) are pretty pog and received decent feedback, and I think (not to boast or anything) I am a good explainer? So I want to contribute with my grade 10 maths knowledge and also practice my english and writing skills in general.

It's free too for the lazy people out there, so you save your time and get your credit while I get my contribution points. Win-win condition (win for the cf readers too).

tldr please read blog title and reply thx

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I would really like a rigorous explanation of the Nim-grundy numbers. I have not studied that topic precisely because there isn't a rigorous source. So if you can write up an article with proofs for everything (I mean everything in game theory which is used in CP), I would like that.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Ah fuck I knew it.

    Sure, it might take a while as I go through my notes while redoing Project Euler once again (essentially) :) but probably doable.

    Thanks for the suggestion!

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I wrote a blog talking about Nim and Grundy numbers here: https://codeforces.me/blog/entry/66040

    I intend to maintain this blog and keep improving its quality over the years, so if there's anything you find lacking, I would love to be able to address it.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Oops, but you can see that I already commented my concerns on your blog some months ago.

      After several replies, I thought that you were missing my point, and that you had no idea what I was trying to ask.

      So I would like grhkm here to try and post a more proof-based treatment of the topic. In fact, this topic seemed so hand-wavy to me that it gave me PTSD and also I am scared of any game-theory problem now, thinking Oh no, what if it is that unrigorous Sprague-Grundy theorem now. Game problems were in the past one of my favorite topics so I would like grhkm to perform some therapy and restore my love for game problems!!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Would you consider this article to be rigorous enough?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, and I have already said why in Shisuko's blog.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm not sure which part is handwavy? Things don't need mathematical formulations and numbers and symbols to be considered rigorous. I mean, we're in CS/comp-prog. Most proofs here are argumentative rather than numerical.

        I showed the proof for Grundy numbers working in a specific example, then pointed out how all the same arguments I made also worked given any directed graph. That's a very common and valid stylistic choice in math writing.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how about combinatorics?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What can I talk about hmm... min/max inclusion-exclusion formula (for expected values)? Burnside's (lmao)? Catalan's (I really have to learn this)?

    I will keep this in mind, but specific might help~

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      burnside would be great, like some hard recursion based on burnside lemma. or even if you suggest me some questions to solve that would be also fine for me.

      → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Burnside's lemma has caused me confusion in the past, although I think I'm more comfortable with it now.

Or really, anything related to graph theory would be great (maybe Hall's marriage theorem or counting labeled teres).

Thanks for being so open to ideas! :)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

i mean a good idea might be creating a syllabus of links and good resources of the math subjects you think are Necessary for CP that will be really appreciated

if you cant i think a general and easy explanation of the applications of matrix exponentiation in calculating some recursive algorithms(like fibonacci) in (log n) time complexity will be helpful(i know some blogs exist on this topic but they seem a little bit to complicated:( )

→ Reply