Qualified's blog

Marathon Threads!
By Qualified, history, 3 years ago, In English

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

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

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

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Commonly seen in fenwick trees, the term -i & i will find the highest power of two i [variable] is divisible by.

Example:

3&-3: 1

6&-6 : 2

18 & -18 : 2

64 & -64: 64

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

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: here

Unfortunately, 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.

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

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

Hint
→ Reply