By duckladydinh, history, 12 months ago, ,

Hallo everyone,

Do you know any simple formulas that are often unknown to many? For me, some can be mentioned are

• Graph: Euler characteristic, Handshaking theorem, Caley Formula, Kirchhoff's theorem, Kőnig's theorem

• Polygon: 2-Ear Theorem, incenter formula of a triangle, pick theorem, Shoelace Formula

• Logic: Pigeonhole

• Prime: Fermat, Wilson's theorem

• Number: McNugget theorem

• Fibonacci: Zeckendorf's theorem

• Counting: Burnside Lemma, stars and bars

• Combinatorics Identity: Vandermonde's Identity, Hockey-stick identity

• Math: Linearity of Expectation

• Other: harmonic series sum

... And what about you? Can you share some?

Thank you.

•
• +92
•

 » 12 months ago, # |   +24 Well I suppose if you included Pigeonhole, then Harmonic Series sum can be included too. It's just useful to know (sometimes used in problems): has an upperbound of
•  » » 12 months ago, # ^ | ← Rev. 2 →   +5 a ha, that is also what I mean, in the past, I never knew why sieve ran so fast until I saw this formulaI will update in the post
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +5 Harmonic Series can be used to explain linearithmic complexity in solution for this problem:http://codeforces.com/problemset/problem/414/BHere is editorial: http://codeforces.com/blog/entry/11470It's n*log(n) because you loop i from 1 up to n, and inside that loop you loop multiples of i up to n, which will run in n/1 + n/2 + ... n/n which is n*(1/1 + 1/2 + ... 1/n) = n*log(n) as Noam527 has described.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 The sieve is well-known. However, something that is not as well-known is that the sieve can be modified to be run in O(n) time. vector is_prime(LIMIT, true); is_prime[0] = is_prime[1] = false; vector primes; for(int i = 2; i < LIMIT; i++) { if(is_prime[i]) primes.push_back(i); for(int j = 0; j < primes.size() && i*primes[j] < LIMIT; j++) { is_prime[i*primes[j]] = false; if(i%primes[j] == 0) break; } }
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   0 Cool. I didn't know that.
•  » » 12 months ago, # ^ |   +9 This is often used in problems. In particular: for (int i = 2; i < N; i++) { for (int j = i; j < N; j += i) { // now i is divisor of j } } let's you create list of all numbers from with their divisors 1..N in .
 » 12 months ago, # |   0 Pick's Theorem is One Such theorem. Problems are there on this topic.
•  » » 12 months ago, # ^ |   0 that's a nice oneI will update in the list :)
 » 12 months ago, # |   +10 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # | ← Rev. 2 →   +30 Chicken McNugget theorem.The motivation is in McDonald Chicken McNuggets, which come in packs of 4, 6, 9, and 20. If you wanted to troll them, you could ask for a pack of 11 (the largest amount of chicken McNuggets they can't make).https://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_TheoremFor two coprime positive integers m and n, that largest number that cannot be written as am + bn (cannot be made by adding up m and n) will be m*n — m — n.Not sure why it works (could not under stand proof :P), so it would be great if some smarter folks expanded on this.
•  » » 12 months ago, # ^ |   +10 Such a formula does exist :o what a surprise?Updated
•  » » » 12 months ago, # ^ |   +3 Yes, unfortunately this only works for two variables. There is no general formula that works for 3+ variables, but there are methods to compute them in polynomial time.As a clarification: numbers that can be made are called chicken mcnugget numbers. Numbers that cannot be made are called Frobenius numbers.Described Here: https://en.wikipedia.org/wiki/Coin_problem
•  » » 12 months ago, # ^ |   +16 It's actually very easy to see that if you look at it as a graph problem. Remainders modulo m are vertices and there are edges from each vertex x to (x+n)%m of length 1, because this is equivalent to adding n once. Now you can see that by reaching shortest path from 0 to a vertex we get the smallest possible number of "+n" parts (crucial here is that adding m doesn't change the remainder modulo m).You can notice that the distances are 1,2,3.. in some order and the last one is exactly m (n-1)-n
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Thank you so much! I've always felt guilty about not getting this but the graphs explanation is much clearer than the maths explanation :P
•  » » » 12 months ago, # ^ |   0 I just tried to draw it out.I am confused about this part "You can notice that the distances are 1,2,3.. in some order and the last one is exactly m (n-1)-n"How could the distance between any two vertices in this graph be m (n-1) — n when the greatest distance possible is m-1? (there are m vertices)
 » 12 months ago, # |   +24 I have found the Shoelace Formula to be extremely useful in some instances (esp with coordinate/geometry problems).A nice trick for determining whether a bunch of points are collinear: if they enclose an area of 0 then they lie on a line or are the same point -- meaning the shoelace formula should give 0 as well.
•  » » 12 months ago, # ^ |   0 :o I use it a lot but I never thought it had a name :pUpdated
 » 12 months ago, # | ← Rev. 2 →   -11 Maybe Faulhaber's Formula for calculating ?Some Pythagorean triplet's properties?
•  » » 12 months ago, # ^ |   +10 I would not really think that it is simple :V
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Interestingly, there are k3logn and k2 solutions to this problem.
•  » » 12 months ago, # ^ |   +1
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -20 nvm, fail
•  » » » » 12 months ago, # ^ |   +10 i = sqrt(-1)I think that what he meant, right?
•  » » » » » 12 months ago, # ^ |   +5 ah yes, thanks, used to j :D
•  » » » 12 months ago, # ^ |   +5 True, but would you mind explaining a bit about its application in CP (some problems for example)Since I rarely see any problems that require complex number directly.
•  » » » » 12 months ago, # ^ |   0 I met a problem 102E - Vectors, whose solution was derived based on complex number. But it does not use the above equation....
•  » » » » 12 months ago, # ^ |   0 Not very sure about CP, but it is neccessary for trig-bashing e.g. Bary Bash.
•  » » » 12 months ago, # ^ |   +16 hahahahha
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   +115 2 + 2 = 4 — 1 = 3 Quick Maths!
•  » » 12 months ago, # ^ |   0 Oh it is too simple!!! but not really unknown to many
•  » » 12 months ago, # ^ |   +5 Maffs*
•  » » » 12 months ago, # ^ |   +16 Man's not hot...
 » 12 months ago, # |   +2 Could you please edit your post and make the theorems point-wise using bullets or something? Right now it looks unpleasant to read.
•  » » 12 months ago, # ^ |   0 done
 » 12 months ago, # | ← Rev. 8 →   +13 Cayley's formula is the number of spanning trees of N nodes which is equal to NN - 2Number of spanning trees in complete bipartite graph GX, Y is : XY - 1 × YX - 1Such thatX : is the number of nodes in the first set.Y : is the number of nodes in the second set.
•  » » 12 months ago, # ^ |   0 nice one :)updated
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   0 I have met a problem about several days before, which used "Fermat's theorem on sums of two squares" (I am not sure of the exact name of this theorem). This theorem has a simple description but perhaps a little bit complicated proof. It states that for any prime integer p > 2, it can be written as p = a2 + b2, where both a and b are positive integers, if and only if p mod 4 = 1.
 » 12 months ago, # |   0 Thanks a lot for your effort. It would be really nice if you also go on adding the links for these theorems. Others might help for the links they found, by commenting.
 » 12 months ago, # | ← Rev. 2 →   +16 Here are few which are used in competitive programming sometimes:
•  » » 12 months ago, # ^ |   0 Could u give me a problem where Jensen's inequality is used... thank you.
•  » » » 12 months ago, # ^ |   0 I never used it in any informatics problem, but much in math problems. Maybe it can be used in proving correctness of solution or reducing some cases while solving problem.
•  » » » 12 months ago, # ^ |   +1 I don't remember any problem, but I have seen it being used to prove quadrangle inequality in divide and conquer DP optimization.
•  » » 12 months ago, # ^ | ← Rev. 3 →   +5 Wow, so many, so nice :DI have updated the blog from some of those, but... not all. For example, I think that the Bertrand's theorem is so obvious. For Goldbach's theorem, I have never really seen a problem that can be "indirectly" solve by it (problems for it are all obviously the definition). Faulhaber's formula, I do not think it is simple in anyway. Jensen's inequality, I think is more suitable for proving rather than implementing. Am I wrong? If so, please just tell me :DAnd Burnside theorem is indeed powerful. That is my motivation for writing this blog
 » 12 months ago, # |   +10 A problem using this theorem: http://codeforces.com/problemset/problem/126/D .The winning strategy for fibonacci nim also uses the theorem.
•  » » 12 months ago, # ^ |   0 That's a very nice one :oI myself also have doubt that it is true but I never try to prove (which I cannot) or bother about it (since not many problems like that anyway). Now I know something new, thank you.
 » 12 months ago, # |   0 I have found the Paleka's lemma to be useful: clickIf and only if it contains "circumcircles" and the intersection of three lines which pass through six distinct points, it can be done using radical center.
•  » » 12 months ago, # ^ |   0 Maybe can you tell me a bit about the problem/situation where you found it helpful? It maybe be very great but for now, I dont really get its usefulness from your discription. Thank you
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   0 Auto comment: topic has been updated by DuckLadyDinh (previous revision, new revision, compare).
 » 12 months ago, # |   0 Ok, maybe all you pros knew it long ago, but I learned inverse mod finding of prime mod with fermat's little theorem just yesterday
•  » » 12 months ago, # ^ |   0 Same ideas :DThe first application I could think of (myself :D) from Fermat theorem is the inverse mode for prime. No other use in programming for it until now :vIt is already included
 » 10 months ago, # |   0 I think you can add Catalan Numbers in Number theory/Combinatorics or Counting.
 » 10 months ago, # |   0 For some reason people don't usually use barycentric coordinates in problems where they can help. Let's say that a point P has masses (x, y, z) wrt triangle ABC with sides a, b, c and angles α, β, γ (side with length a has endpoints B and C, angle α is , the same naming with other sides and angles) if x + y + z ≠ 0 and (x + y + z)P = xA + yB + zC. This can help to find some points associated to a triangle: centroid has masses (1, 1, 1), incenter has masses (a, b, c), excenters have masses ( - a, b, c), (a,  - b, c), (a, b,  - c), orthocenter has masses or (if you don't want to mess with infinity) ((a2 + b2 - c2)(a2 - b2 + c2), ...) or (acosβcosγ, ...), if one point has masses (x, y, z) then its isotomic conjugate has masses (a2 / x, b2 / y, c2 / z), which instantly gives us masses of the circumcenter, Steiner point (also known as Fermat point or Torricelli point) is either the vertex of angle which exceeds , or (if there is no such angle in the triangle) has masses (a / sin(α + π / 3), ...). I use "masses" instead of "barycentric coordinates" since the sum of barycentric coordinates should equal 1. The points listed above can be found in one line if one has a written Point class with addition and multiplication by a real. Of course, sometimes (for example, for orthocenter of circumcenter) it's easier to intersect two lines, but there are problems where masses optimize time and efforts.