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 .
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
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
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!
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.
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.
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
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}$$$.
Okay, first thing first, how did you get this equation,
(2n + 3)^2 ≡ −11 (mod 121)
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??
Got it, thanks!! Now, I'll try to understand following 2 points!
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?
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??
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.
https://www.hmmt.co/archive/problems/
Which should you focus on?
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.
I think combinatorial problems and exersises by lovas is good for competitive programming.