MasterMind0108's blog

Good mathematics resources/books/tutorials for competitive programming
By MasterMind0108, history, 7 years ago, In English

Hello! I'm interested in math and geometry recently, if some of you have good resources/books/tutorials for maths in competitive programming. Thank you very much ^^ .

P.S: This is my first post on Codeforces. If I cause any inconvience please forgive me :D . Sorry for my bad english :P .

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

Comments Comments (14)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

  • AOPS

  • Number theory: Titu Andreescu 104 Number Theory problems; WACLAW SIERPINSKI 250 Problems in Elementary Number Theory — Sierpinski (1970); Titu Andreescu, Dorin Andrica., Number Theory Structures, Examples, and Problems

  • Combinatorics: Titu Andreescu 102 Combinatorical problems

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hey, I have recently started reading Number Theory Structures, Examples, and Problems, after finding this resource, thanks for it. I was going through the material, and I have question if you don't mind...

    Problem 1.1.1. Prove that for all integers n, n^2 + 3n + 5 is not divisible by 121. So the equation is re-written as,

    let's start with 11 - n^2 + 3n + 5 = (n + 7)(n − 4) + 33 and explanation follows, 33 is divisible by 11 and assume (n + 7)(n − 4), which implies either (n + 7) is divisible by 11 or (n — 4) is divisible by 11 but( and this is the part which I don't understand, is this property or something?! ), since, (n — 7) — (n — 4) = 11, both (n — 7) and (n — 4) must be divisible by 11. (because that's basically make the base of the proof.)

    More formally, if x | a * b and a — b = x, then x | a and x | b. Is this true?

    Thanks in advance!

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

      This is false. If you eliminate the variable $$$a$$$, you have $$$x | ab = bx + b^2$$$ so $$$x | b^2$$$. Similarly you can show $$$x | a^2$$$. However, this doesn't say anything about $$$x$$$ dividing $$$a$$$ or $$$b$$$. An example where this is false is when $$$x = 4$$$, $$$a = 6$$$ and $$$b = 2$$$. But when $$$x$$$ is a prime, then $$$x | a^2$$$ means $$$x | a$$$ because of prime factorization.

      → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      you can solve it using quadratic equation , proof by contradiction assume it is divisible

      n^2 + 3n + 5 = 121p, p is an integer

      n^2 + 3n + 5 — 121p , should have integer roots

      now we know roots are (-b +- root(b^2-4ac)) / 2a

      but b^2 — 4ac = 4.121p — 11 = 11 . ( 44p — 1) = k^2 lets say, k>=0

      now there are three cases k^2 = 1.1 or 11.11 this is pretty simple to prove

      third one is some term combined with 11 that is factor of 44p — 1. it means 44p — 1 = 0 mod 11 which is false.

      for k < 0 , it is similar.

      hence all the cases are false, and it is contradicting our assumption.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        aonther way is to

        from the n^2 + 3n + 5 — 121p, start working under modulo 11

        n^2 + 3n + 5 = 0 mod 11

        and none of the values from n = [0,11) satisfy this , so we are good with this.

        edit: my mistake n = 4 satisfies this. so we cannot use this

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

          It's still possible to solve it using a similar idea. Note that the condition boils down to $$$(2n+3)^2 \equiv -11 \pmod{121}$$$.

          • Taking the first approach, this means $$$(2n + 3)^2$$$ is divisible by $$$11$$$, so $$$11$$$ must divide $$$2n + 3$$$ since $$$11$$$ is prime, so $$$(2n + 3)^2 \equiv 0 \pmod{121}$$$, which is a contradiction.
          • To get to the same conclusion using an approach similar to yours, consider this equation modulo $$$11$$$ first. Checking all values of $$$x = 2n + 3$$$ modulo $$$11$$$, this is only possible when $$$x \equiv 0 \pmod{11}$$$. So we have $$$x = 11k$$$, and thus $$$x^2 = 121k^2 \equiv 0 \pmod{121}$$$.
          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Okay, first thing first, how did you get this equation,

            (2n + 3)^2 ≡ −11 (mod 121)

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

              for this he just multiplied the modulo by 4 on both side.

              n^2 + 3n + 5 = 0 mod 121

              (n + 3/2)^2 + 5 — (3/2)^2 = 0 mod 121

              (2n + 3)^2 + 20 — 9 = 0 mod 121 got it??

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

        I have tried this approach, but couldn't make anything out of 44p — 1 and still am little bit confused there, can you elaborate.

        My logic was since we have 11 * (44p — 1), so to have integer out of square root, we should have 11 * perfect_square = 44p — 1, which will bring 11 out of root and another integer which will be square root of perfect square, so that n(roots) of equation are integers, can you think about this?

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

          for this so as far you understand 11 * (44p — 1) is a perfect square.

          so lets say

          x * y = 1 * 11 * (44p — 1)

          symmetrically assume three cases

          x = 1, x = 11, and x = 11 * p , y = (44p — 1) / (some number q)

          but as x = y , they must have all equal divisors , so 11 divides x , it means it should divide y too. but if even without dividing by q, if its not divisible like (44p — 1) % 11 = -1 = 10.

          so even after dividing with q it will not be divisible.

          got it??

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

I suggest checking out some material (only the easy stuff) from mathematical olympiads. My background is in mathematical olympiads, and it helped immensely with competitive programming.

I can't link any material though, because all of it was in German. And we received printed copies back than.

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

There isn't Math for 'competitive programming', per se. But there are books for Math contests and problem solving and they indirectly help.

On the more advanced side, a book like Generatingfunctionology by Herbert Wilf can be useful.

If you're a beginner, I recommend the book Mathematical Circles. It is a fantastic book and a great introduction to problem solving ! Let me know about your level if this book is easy for you. I will recommend more books to you accordingly.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think combinatorial problems and exersises by lovas is good for competitive programming.

→ Reply