### Qualified's blog

By Qualified, history, 5 weeks ago,

Inspired by AoPS's Marathon Threads, I decided to create one on CF! The only rule of this forum is that you have post an interesting theorem, or trick related to CP or math, with a brief description and provide a source for extra research.

To start things off, I think that Proizvolov's identity is very interesting (but doesn't appear much in math problems :( ) and states if you have the numbers from $1-2n$ and split the numbers into 2 sets $A, B$ such that $A$ is in increasing order and $B$ is in decreasing order, the sum $|A_1-B_1|+|A_2-B_2|+\dots+|A_n-B_n|$ is always equal to $n^2$. Source: https://en.wikipedia.org/wiki/Proizvolov%27s_identity

• +28

 » 5 weeks ago, # | ← Rev. 2 →   +5 Euler's fornula for planar graphs:$V - E + F = 2$, where $V$ is the number of vertices, $E$ is the number of edges and $F$ is the number of faces.link
•  » » 5 weeks ago, # ^ |   +12 Note that this formula only holds for connected graphs. The more general formula is$V - E + F = 1 + C$where $C$ is the number of connected components. I've made the mistake of forgetting the connected condition when solving a few problems on disconnected planar graphs.
 » 5 weeks ago, # | ← Rev. 2 →   +3 Commonly seen in fenwick trees, the term -i & i will find the highest power of two i [variable] is divisible by.Example:3&-3: 16&-6 : 218 & -18 : 264 & -64: 64
 » 5 weeks ago, # |   0 Quadratic Reciprocity: $\left( \frac{p}{q} \right) \cdot \left( \frac{p}{q} \right) = (-1)^{\frac{(p - 1) \cdot (q - 1)}{2}},$where the notation means the legendre symbol, rather than fractions.See Reference 1 and Reference 2 for proofs.I think I remember reading somewhere that there are over 100 proofs of quadratic reciprocity and Gauss allegedly called it the golden theorem. There's even presumably a dissertation on quadratic residues, here, but it goes way beyond quadratic reciprocity.Towards the end of Petr's blog, he also briefly mentioned an interesting problem involved (hidden) quadratic residues from OpenCup: hereUnfortunately, I don't think this is used in math competitions that much :((. At least, I've only seen it used in competitions once (I think it was some old Romanian TST question, maybe not). Math contests have been slowly drifting away from number theory rip.
 » 5 weeks ago, # |   +10 I have seen Proizvolov's identity twice once on CF and once on TC. I didn't know it has a name. Codeforces and Topcoder. Loved it when saw it for the first time. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~To follow the rules of this thread, here are my favourite facts -Let $b$ be a sequence of length $M$. If the median of $b$ is $x$,- $b$ contains $\lceil \frac{M}{2} \rceil$ elements that are greater than or equal to $x$.- $x$ is the largest possible value that satisfies the condition above.How to exploit this fact? — https://atcoder.jp/contests/arc101/tasks/arc101_b~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$|x-x_1|+|x-x_2|+ \cdots + |x-x_n|$ is minimum at median of multiset $(x_1,x_2, \cdots , x_n)$.Something similar for trees do exists — https://atcoder.jp/contests/arc087/tasks/arc087_d HintCentroid