Double Counting Notes by Victoria Krakovna
by SomeonecoolLovesMaths, Mar 12, 2025, 2:46 PM
In many combinatorics problems, it is useful to count a quantity in two ways. Let’s start with a simple example.
(Iran 2010 \#2) There are 
points in the plane such that no three of them are collinear. Prove that the number of triangles, whose vertices are chosen from these points and whose area is 
, is not greater than 
.
Let the number of such triangles be 
. For each edge between two points in the set we count the number of triangles it is part of. Let the total number over all edges be 
.
On the one hand, for any edge
, there are at most 
points such that the triangles they form with 
and 
have the same area. This is because those points have to be the same distance from line , and no three of them are collinear. Thus, 
. On the other hand, each triangle has 
edges, so 
. Thus,
![\[
k \leq \frac{T}{3} \leq \frac{4}{3} \binom{n}{2} = \frac{2}{3}(n^2 - n).
\]](//latex.artofproblemsolving.com/5/7/5/57549da7e5a31d84d6c9ed82afd51b5f57f68e75.png)
It’s a good idea to consider double counting if the problem involves a pairing like students and committees, or an array of numbers; it’s also often useful in graph theory problems.
(IMO 1987 #1) Let 
be the number of permutations of the set 
which have exactly fixed points. Prove that
![\[
\sum_{k=0}^{n} k \cdot p_n(k) = n!.
\]](//latex.artofproblemsolving.com/5/a/3/5a33870a43bd98f6e60b2a4df907ca0cb3675435.png)
The first idea that might occur here would be to find , then multiply it by , sum it up… probably resulting in a big expression. However, if we look at the required result, we see that it suggests a natural counting — the left-hand side is the total number of fixed points over all permutations. Another way to obtain that is to consider that each element of is a fixed point in 
permutations, so the total is 
. (Note that we are counting pairs of the form (point, permutation) such that the point is a fixed point of the permutation.) 
(China Hong Kong MO 2007) In a school there are 2007 girls and 2007 boys. Each student joins no more than 100 clubs in the school. It is known that any two students of opposite genders have joined at least one common club. Show that there is a club with at least 11 boys and 11 girls.
Since we are only given information about club membership of students of different gender, this suggests that we should consider triples of the form (boy, girl, club), where the boy and girl both attend the club. Let the total number of such triples be .
For each pair (boy, girl), we know that they attend at least one club together, so since there are
such pairs,
![\[
T \ge 2007^2 \cdot 1.
\]](//latex.artofproblemsolving.com/9/a/4/9a40daed5003e91e392e6a9a5f0c7ed0eb7de53e.png)
Assume that there is no club with at least 11 boys and 11 girls. Let
be the number of triples involving clubs with at most 10 boys, and 
be the number of triples involving clubs with at most 10 girls. Since any student is in at most 100 clubs, the number of (girl, club) pairs is at most 
, so 
. Similarly, 
. Then,
![\[
2007^2 \le T \le X + Y \le 2 \cdot 2007 \cdot 1000 = 2007 \cdot 2000
\]](//latex.artofproblemsolving.com/8/8/7/8874e043afee1a11735de033e2f40cfd9802c6e5.png)
which is a contradiction.
If 
is an integer and 
is a prime, then
![\[
a^p \equiv a \pmod{p}.
\]](//latex.artofproblemsolving.com/9/a/d/9adaf16e16bc3b65a4dd4930d8e6975955e70b24.png)
Consider the set of strings of length using an alphabet with different symbols. Note that these strings can be separated into equivalence classes, where two strings are equivalent if they are rotations of each other. Here is an example of such an equivalence class (called a "necklace") for 
:
![\[
\{ \text{BCCCB}, \text{CCBCB}, \text{CBBCC}, \text{BBCCC}, \text{CCCBB} \}.
\]](//latex.artofproblemsolving.com/5/f/5/5f5c655e300391e559515243b47f46e3f6a408ec.png)
Let’s call a string with at least two distinct symbols in it \textit{non-trivial}. All the rotations of a non-trivial string are distinct — since is prime, a string cannot consist of several identical substrings of size greater than . Thus, all the equivalence classes have size , except for those formed from a trivial string, which have size .
Thus, there are two ways to count the number of non-trivial strings. Since there are
strings in total, of which are trivial, we have 
non-trivial strings. Also, the number of non-trivial strings is times the number of equivalence classes formed by non-trivial strings. Therefore, divides .
might contain mistakes
(Iran 2010 \#2) There are 
points in the plane such that no three of them are collinear. Prove that the number of triangles, whose vertices are chosen from these points and whose area is 
, is not greater than 
.
Let the number of such triangles be 
. For each edge between two points in the set we count the number of triangles it is part of. Let the total number over all edges be 
.On the one hand, for any edge
, there are at most 
points such that the triangles they form with 
and 
have the same area. This is because those points have to be the same distance from line , and no three of them are collinear. Thus, 
. On the other hand, each triangle has 
edges, so 
. Thus,![\[
k \leq \frac{T}{3} \leq \frac{4}{3} \binom{n}{2} = \frac{2}{3}(n^2 - n).
\]](http://latex.artofproblemsolving.com/5/7/5/57549da7e5a31d84d6c9ed82afd51b5f57f68e75.png)
It’s a good idea to consider double counting if the problem involves a pairing like students and committees, or an array of numbers; it’s also often useful in graph theory problems.
(IMO 1987 #1) Let 
be the number of permutations of the set 
which have exactly fixed points. Prove that![\[
\sum_{k=0}^{n} k \cdot p_n(k) = n!.
\]](http://latex.artofproblemsolving.com/5/a/3/5a33870a43bd98f6e60b2a4df907ca0cb3675435.png)
The first idea that might occur here would be to find , then multiply it by , sum it up… probably resulting in a big expression. However, if we look at the required result, we see that it suggests a natural counting — the left-hand side is the total number of fixed points over all permutations. Another way to obtain that is to consider that each element of is a fixed point in 
permutations, so the total is 
. (Note that we are counting pairs of the form (point, permutation) such that the point is a fixed point of the permutation.) 
(China Hong Kong MO 2007) In a school there are 2007 girls and 2007 boys. Each student joins no more than 100 clubs in the school. It is known that any two students of opposite genders have joined at least one common club. Show that there is a club with at least 11 boys and 11 girls. Since we are only given information about club membership of students of different gender, this suggests that we should consider triples of the form (boy, girl, club), where the boy and girl both attend the club. Let the total number of such triples be .For each pair (boy, girl), we know that they attend at least one club together, so since there are
such pairs,![\[
T \ge 2007^2 \cdot 1.
\]](http://latex.artofproblemsolving.com/9/a/4/9a40daed5003e91e392e6a9a5f0c7ed0eb7de53e.png)
Assume that there is no club with at least 11 boys and 11 girls. Let
be the number of triples involving clubs with at most 10 boys, and 
be the number of triples involving clubs with at most 10 girls. Since any student is in at most 100 clubs, the number of (girl, club) pairs is at most 
, so 
. Similarly, 
. Then,![\[
2007^2 \le T \le X + Y \le 2 \cdot 2007 \cdot 1000 = 2007 \cdot 2000
\]](http://latex.artofproblemsolving.com/8/8/7/8874e043afee1a11735de033e2f40cfd9802c6e5.png)
which is a contradiction. 
If 
is an integer and 
is a prime, then![\[
a^p \equiv a \pmod{p}.
\]](http://latex.artofproblemsolving.com/9/a/d/9adaf16e16bc3b65a4dd4930d8e6975955e70b24.png)
Consider the set of strings of length using an alphabet with different symbols. Note that these strings can be separated into equivalence classes, where two strings are equivalent if they are rotations of each other. Here is an example of such an equivalence class (called a "necklace") for 
:![\[
\{ \text{BCCCB}, \text{CCBCB}, \text{CBBCC}, \text{BBCCC}, \text{CCCBB} \}.
\]](http://latex.artofproblemsolving.com/5/f/5/5f5c655e300391e559515243b47f46e3f6a408ec.png)
Let’s call a string with at least two distinct symbols in it \textit{non-trivial}. All the rotations of a non-trivial string are distinct — since
is prime, a string cannot consist of several identical substrings of size greater than . Thus, all the equivalence classes have size , except for those formed from a trivial string, which have size .Thus, there are two ways to count the number of non-trivial strings. Since there are
strings in total, of which are trivial, we have 
non-trivial strings. Also, the number of non-trivial strings is times the number of equivalence classes formed by non-trivial strings. Therefore, divides . might contain mistakes
![$$
\text{(Reverse for } r\in[0,1]\text{)}
$$](http://latex.artofproblemsolving.com/b/4/a/b4a0c999f6228c031f0f498db8748163e853d3e0.png)
![$$
(1+x)^r \le 1 + (2r-1)x,\quad x\in[0,1],\; r\in\mathbb{R}\setminus(0,1).
$$](http://latex.artofproblemsolving.com/3/a/a/3aa126b0efac08c184132b3e428908db3858896c.png)
![$$
x^{\frac{1}{r}}(x-1) \le r\,x\Bigl(x^{\frac{1}{r}}-1\Bigr), \quad x,r\ge 1, \quad 2^{-x} \le 1 - x^2, \quad x\in[0,1].
$$](http://latex.artofproblemsolving.com/f/e/9/fe99ecded3f3a45c7ec1b59cef0eb688daa446ba.png)
![$$
e^{-x} \le 1 - x^2, \quad x\in [0,1.59], \quad e^x \le 1+x+x^2, \quad x<1.79.
$$](http://latex.artofproblemsolving.com/f/6/8/f6800b55a67a2b56aa34db48de6118c1de68410b.png)
![$$
\max\left\{\frac{2}{\pi},\frac{\pi^2-x^2}{\pi^2+x^2}\right\} \le \frac{\sin x}{x} \le \cos^2 x \le 1 \le 1+\frac{x^2}{3} \le \frac{\tan x}{x}, \quad x\in\left[0,\frac{\pi}{2}\right].
$$](http://latex.artofproblemsolving.com/f/9/c/f9caa9a564dfd20ae3e4b962d5a5322b98529275.png)
![$$
\frac{x_1 + x_2 + \dots + x_n}{n} \ge \sqrt[n]{x_1 x_2 \dots x_n} \ge
\frac{n}{\frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_n}}.
$$](http://latex.artofproblemsolving.com/0/c/9/0c987158fd6e2e3c5f4aef6b92f396b7ca5f75f2.png)
![$$
\frac{x+y+z}{3} \ge \sqrt[3]{xyz} \ge \frac{3xyz}{xy+yz+zx}.
$$](http://latex.artofproblemsolving.com/2/1/2/21266f631485bdbc7ed74b28900ea7a378f8fe14.png)
![$$
\Pr(|X| \geq a) \leq \frac{E[|X|]}{a}, \quad a > 0 \quad \text{(Markov's Inequality)}
$$](http://latex.artofproblemsolving.com/a/6/a/a6a3712dc88152eda699dfa81a469fad1e96bdf5.png)
![$$
\Pr(|X - E[X]| \geq t) \leq \frac{\operatorname{Var}(X)}{t^2}, \quad t > 0 \quad \text{(Chebyshev's Inequality)}
$$](http://latex.artofproblemsolving.com/1/1/7/117e416cf10e0579969f46fdc0ef4c5796f802dc.png)
![$$
\Pr(|X - \mathbb{E}[X]| \geq \delta) \leq 2\exp\left(-\frac{2\delta^2}{\sum_{i=1}^{n} (b_i - a_i)^2}\right),
$$](http://latex.artofproblemsolving.com/6/1/5/6157394ff615bd0c0a877a3000be4c872e533ae3.png)
![$$
\text{for independent } X_i \text{ with } X_i \in [a_i, b_i] \quad \text{(Hoeffding's Inequality)}.
$$](http://latex.artofproblemsolving.com/1/b/4/1b4111b2c4e1ef3b6ef3fc4b1b798ae2cdc509ca.png)
![$$
\Pr\left(S_n - E[S_n] \geq t\right) \leq \exp\left(\frac{-t^2}{2(\sigma^2 + Rt/3)}\right),
$$](http://latex.artofproblemsolving.com/3/2/e/32e0849cf7c5122be2a329b614858e9d27f271cc.png)
![$$
\text{for i.i.d. } X_i \text{ with } |X_i - E[X_i]| \leq R \text{ and variance } \sigma^2.
$$](http://latex.artofproblemsolving.com/a/b/b/abb1f4e3fb3bc01b8de732ae92b8695f9d388ac2.png)
![$$
\Pr(S_n \geq (1+\delta)E[S_n]) \leq \exp\left(-\frac{\delta^2}{2+\delta} E[S_n]\right),
$$](http://latex.artofproblemsolving.com/7/1/b/71b6b13e29ed2a507ff2563062d6f1efa1e65936.png)
![$$
\Pr(S_n \leq (1-\delta)E[S_n]) \leq \exp\left(-\frac{\delta^2}{2} E[S_n]\right),
$$](http://latex.artofproblemsolving.com/f/5/3/f53513a5af6dec65bbd4d36683a2e57ba0ff2ff0.png)
![$$
\text{for independent } X_i \text{ taking values in } [0,1].
$$](http://latex.artofproblemsolving.com/7/0/9/7094de97d6c2aa62838dba9d2035f46a1e7b566e.png)
![$$
\Pr(|S_n - E[S_n]| \geq t) \leq 2\exp\left(-\frac{t^2}{2 \sum_{i=1}^{n} c_i^2}\right),
$$](http://latex.artofproblemsolving.com/d/f/0/df03ae8908fbaf3875ff9778e2edcce35dd82a0b.png)
![$$
\varphi(\mathbb{E}[X]) \leq \mathbb{E}[\varphi(X)],
$$](http://latex.artofproblemsolving.com/f/e/4/fe44f8fdac14f857c290f93eaa52eab7e5e2962c.png)
such that![\[
f(n) \ge n + (-1)^n,\quad \forall n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/1/7/e/17e1f167da6f5bc998907aa08248821f513eb182.png)
such that for any real numbers 
and 
![\[
g(x+y) + g(x)g(y) = g(xy) + g(x) + g(y).
\]](http://latex.artofproblemsolving.com/9/b/5/9b5d3eef8ab320996044c23fb3c4a497b56567ca.png)
such that for every real 
![\[
f(x^2-y^2) = xf(x) - yf(y).
\]](http://latex.artofproblemsolving.com/8/7/c/87cbd6cfddaa21a762ee30fd2031ca29bf8ed9c4.png)
![\[
f\bigl(xf(x) + f(y)\bigr) = f(x)^2 + y.
\]](http://latex.artofproblemsolving.com/0/0/2/002c970941166d01c1d82a832f8fc405456c2751.png)
![\[
f(f(n)) + (f(n))^2 = n^2 + 3n + 3,\quad \forall n\in\mathbb{N}.
\]](http://latex.artofproblemsolving.com/6/c/e/6ce78ec26d2f644fcc3454e600685a662e8c2952.png)
be a positive integer. Find all strictly increasing functions 
such that the equation![\[
\frac{f(x)}{n} = k - x
\]](http://latex.artofproblemsolving.com/7/6/b/76bbfb5c92bca0aad5dced4404c8822f490c452a.png)
has an integral solution 
.
such that![\[
f\Bigl(\frac{x+y}{2}\Bigr) = \frac{2f(x)f(y)}{f(x)+f(y)} \quad \forall x,y \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/1/7/7/1779a0e94b6fad59c45602b9c8a1dd948f05273e.png)
such that![\[
f(1-x) = 1 - f(f(x)) \quad \forall x \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/5/9/1/5915372df04a4a5035b77a9f7f20cd42985f51fa.png)
![\[
f(1+xf(y)) = yf(x+y) \quad \forall x,y \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/e/8/3/e8347628ef368802b4553fd97401ffb358418d23.png)
![\[
f(xf(y)) = f(x+y) \quad \forall x,y \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/5/f/d/5fdebae1b344c74e686503013ce6d3297a84937f.png)
![\[
f\bigl(f(x)+y\bigr) = f\bigl(x^2-y\bigr) + 4yf(x) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/4/e/a/4ea71eb67ec57b8b35229e95adf4e8e1993d694e.png)
such that![\[
f(x+y) + g(x-y) = 2h(x) + 2h(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/5/c/b5c6a0445ecdcb65834e2797dab2c23f12831d49.png)
![\[
f(x+y+z) = f(x) \cdot f(1-y) + f(y) \cdot f(1-z) + f(z) \cdot f(1-x) \quad \forall x,y,z \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/4/5/d/45d7c21f5427ff8295eae6b96d35a54e5850ecf3.png)
![\[
f\bigl(f(x)-f(y)\bigr) = (x-y)^2\,f(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/8/c/a/8ca75379896e8e3b4eb228c5f97e57747a86fcf0.png)
such that
,
;
,![\[
f(xy) = g(y)f(x) + f(y).
\]](http://latex.artofproblemsolving.com/7/2/5/725cc8a1d4bdeee26436966e1cb91f19cf24cb29.png)
16. Find all functions ![\[
f\bigl((x+z)(y+z)\bigr) = \bigl(f(x)+f(z)\bigr)\bigl(f(y)+f(z)\bigr) \quad \forall x,y,z \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/0/b/d/0bd748c833014ff90f634cae4a1935be175405ca.png)
![\[
f(x^3+y^3) = x^2f(x) + yf(y^2) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/c/b/dcb4128e28062ceb2014d5f2f05a1b99dc4d7b5c.png)
![\[
f(m+nf(m)) = f(m) + m\,f(n) \quad \forall m,n \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/0/5/1/0513ba8c759fb51014808e155a73bf25d9c34c69.png)
![\[
f(x)\,f(y) = f(x+y) + xy \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/f/0/bf0ad5a89960e879426dd70274186fcfc23eecb6.png)
such that![\[
x\cdot 3f(y) \text{ divides } f(x)\cdot 3y \quad \forall x,y \in \mathbb{N}\cup\{0\}.
\]](http://latex.artofproblemsolving.com/4/4/1/4415aaab86dcd897a4a70010d70fe093f270eca2.png)
![\[
f(x+y)\,f(x-y) = \bigl(f(x)f(y)\bigr)^2 \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/8/3/7/837bfff61ca2cbe4a4b661f675e5435d839bb747.png)
![\[
(x+y)\Bigl(f(x)-f(y)\Bigr) = (x-y)f(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/0/9/f/09fd0c7227daf5bd27fab95371b54c22bd938e7d.png)
![\[
f\bigl(f(x)+y\bigr) = f\bigl(x^2-y\bigr) + 4f(x)y \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/6/d/d6d302f63c2452b1234759065d27e0968794ac37.png)
such that![\[
f(m+n-mn) = f(m)+f(n)-f(mn) \quad \forall m,n \in \mathbb{Z}.
\]](http://latex.artofproblemsolving.com/b/7/8/b782620379d0118152e2cc58d0010da3423599d2.png)
such that 
and![\[
\Bigl(f(ab)\Bigr)^2 = \Bigl(af(b)+f(a)\Bigr)\Bigl(bf(a)+f(b)\Bigr) \quad \forall a,b \in (0,1).
\]](http://latex.artofproblemsolving.com/0/f/2/0f2d0a333bdd73ff468072cfd716f94865385710.png)
such that![\[
f(x+y+f(x)) = x+f(x)+f(y) \quad \forall x,y \in \mathbb{Q}.
\]](http://latex.artofproblemsolving.com/c/2/4/c24abf59bf7cf9c3e2507cdf1bab05309fb2c57c.png)
![\[
f(x^2+f(y)) = (x-y)^2\,f(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/8/e/c/8ec784f0072dc541075e0b385716e1d7e87e74f0.png)
![\[
\begin{cases}
f(x+y)=f(x)+f(y), & \forall x,y \in \mathbb{R},\\[1mm]
f(x)=x^2\,f\Bigl(\frac{1}{x}\Bigr), & \forall x\in \mathbb{R}\setminus\{0\}.
\end{cases}
\]](http://latex.artofproblemsolving.com/e/9/9/e99289d2daa77add553d408daf3be38d875e2383.png)
be a real number. Find all functions ![\[
f(f(x)) + a = x^2 \quad \forall x \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/0/6/b06fb6b36f70dd602d503c01d9fcb4ad4c5fb253.png)
![\[
f(f(n)) \le \frac{n+f(n)}{2} \quad \forall n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/c/2/5/c254eb6b8404999b6bfa3771fb789ce2c45a58f0.png)
such that![\[
f(x^2)+f(y^2) = \Bigl[q(x)-q(y)\Bigr]\,g(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/0/1/5/01513c2bee2e2cd14cf5cbeb6c4735ece4382adb.png)
![\[
f(x+y)+f(x-y)=2f(x)\cos y \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/4/3/0/430eaf5df84e7f8fdad85ddc77e123d1529c753e.png)
![\[
f(x-f(y)) = f(x) + x\,f(y) + f(f(y)) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/6/7/0/670cce9fd7887071b77fd8933fcd13a16577eff6.png)
![\[
f(f(x)) = 6x - f(x) \quad \forall x \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/a/c/1/ac188f5afc80857b95aea85dce5b1c0d8dbfcbf2.png)
![\[
f(x+y)+f(xy)+1 = f(x)+f(y)+f(xy+1) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/f/a/dfa0e1cb440806b5b155be8f1c3b7692766f57c7.png)
![\[
x^2y^2\Bigl(f(x+y)-f(x)-f(y)\Bigr) = 3(x+y)f(x)f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/9/a/d9af0e9489f3da73891026014dc5d5d9d5161197.png)
![\[
f\bigl(x^3+y^3\bigr) = x\,f(x^2) + y\,f(y^2) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/f/b/1/fb1a28a862c1030fc734a3e035b1f1a8197685aa.png)
such that![\[
\lvert f(x)-f(y) \rvert \le (x-y)^2 \quad \forall x,y \in \mathbb{Q}.
\]](http://latex.artofproblemsolving.com/6/a/3/6a3b91fc70b5e8dc2a2610a6c1817630bf858f3c.png)
such that![\[
f(x+y)=f(x^2+y^2) \quad \forall x \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/b/a/a/baaeca4c41cdb240fcb92380301b791dcee2f870.png)
![\[
x^2y^2\Bigl(f(x+y)-f(x)-f(y)\Bigr)=3(x+y)f(x)f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/f/7/b/f7b1889dc91cc651151fa91107454e5b40e4213f.png)
![\[
f\bigl(f(x)+f(y)+f(z)\bigr)=f\bigl(f(x)-f(y)\bigr)+f\bigl(2xy+f(z)\bigr)+2f(xz-yz) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/f/e/a/fea22506b79ce9e1216c201e2069ae5c2c050c58.png)
![\[
m^2+f(n) \mid f(m)^2+n \quad \forall m,n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/3/2/8/328c27cdf8dc3a0842659d38bf76ee0df3411d9f.png)
![\[
f(x+f(y)) = f(x)+y^n \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/4/3/c/43cb53e970ffa0026fe768762e5977d721edef89.png)
![\[
3f\bigl(f(f(n))\bigr) + 2f\bigl(f(n)\bigr) + f(n) = 6n \quad \forall n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/2/0/0/2004b25f1cc76fd9c05b43446183ed2f09e843a8.png)
![\[
\Bigl(f^2(m)+f(n)\Bigr) \mid \Bigl(m^2+n^2\Bigr)^2 \quad \forall m,n \in \mathbb{N}^*.
\]](http://latex.artofproblemsolving.com/b/8/1/b813a150a4acbcdc78e9435be8a928505b2f2cf9.png)
![\[
f\Bigl(\frac{2xy}{x+y}\Bigr) = \frac{2f(x)f(y)}{f(x)+f(y)} \quad \forall x,y \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/0/a/a/0aaf9e3106319815dee043aef66ee87d0cd4655d.png)
![\[
f(xy) = \max\{f(x),y\} + \min\{f(y),x\} \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/8/9/8/898f4cc9a12f22a9dbf6a841d962ff767aafea18.png)
![\[
\begin{cases}
f(x+f(y)) = y+f(x) & \forall x,y \in \mathbb{R}, \\
\{f(x)/x : x \in \mathbb{R}\} \text{ is finite.}
\end{cases}
\]](http://latex.artofproblemsolving.com/0/1/1/011ed5bade884f5b8bde3f7e9a826c851aca5ad2.png)
![\[
f\bigl(f(x)+f(y)\bigr)+f\bigl(f(x)\bigr)=2f(x)+y \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/e/1/de111700fc93cbc2801401b7aa720f041b1c3002.png)
![\[
f\Bigl(x^2(z^2+1)+f(y)(z+1)\Bigr)=1-f(z)(x^2+f(y))-z\Bigl((1+z)x^2+2f(y)\Bigr) \quad \forall x,y,z \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/c/7/2/c72d495f8ffbfcd3bbcc0e043afe27a48a96ffed.png)
such that![\[
f(mn)=f(m)+f(n)+3f(m)f(n).
\]](http://latex.artofproblemsolving.com/9/b/c/9bcc5dd4da7aeebda4b0c863d6ffb47a6f17ea01.png)
![\[
f\bigl(x-f(y)\bigr)=f\bigl(f(y)\bigr)+x\,f(y)+f(x)-1 \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/9/8/b988c8871343953e36b01084a27212db91c1c662.png)
![\[
f\bigl(xf(x+y)\bigr)=f\bigl(yf(x)\bigr)+x^2 \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/9/4/f/94f7427a305995800a959b4eea31f469971bd48c.png)
![\[
f\Bigl(x^2+\frac{x}{3}+\frac{1}{9}\Bigr)=f(x) \quad \forall x \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/4/f/d4ff3478072906c4bbe81aaa8c16ed5616bea738.png)
,![\[
f\bigl(f(x)\bigr)=f(x)+px \quad \forall x \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/7/d/1/7d1e7bbaf4a491517b8023cb27e06f0a7aa4ff77.png)
![\[
f\bigl(x+xy+f(y)\bigr)=\Bigl(f(x)+\frac{1}{2}\Bigr)\Bigl(f(y)+\frac{1}{2}\Bigr) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/f/0/e/f0ed193bccf25b1a615c5f5c8ab9f41c972d0a30.png)
![\[
f\bigl(f(x)+y\bigr)=f(x+y)+x\,f(y)-xy-x+1 \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/c/8/bc8d3d157e3b6e3190be5ce1214d9981a57d557a.png)
![\[
x\Bigl(f(x)+f(-x)+2\Bigr)+2f(-x)=0 \quad \forall x \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/2/5/1/251b66173c96c55c9ecbeb45a2cc530493a2e59a.png)
such that for each 
![\[
f\Bigl(x+f(x)^2+y\Bigr)=2x-f(x)+f\bigl(f(y)\bigr).
\]](http://latex.artofproblemsolving.com/b/3/b/b3b76b716885d2e9567bac42ed1525850b10adf2.png)
![\[
(1+f(x)f(y))\,f(x+y)=f(x)+f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/5/5/7/557d5637df67580e90970b74cf171794c5ee9786.png)
![\[
f(x^2+x+3)+2\,f(x^2-3x+5)=6x^2-10x+17,
\]](http://latex.artofproblemsolving.com/0/2/9/029da5d6bb536051948d8a4bf3fed6165569d6b3.png)
calculate 
.![\[
f\Bigl(f(x)y+\frac{x}{y}\Bigr)=(f(x))^n+y+f(y) \quad \forall x,y \in \mathbb{R},\; n\in\mathbb{Z}_{\ge2}.
\]](http://latex.artofproblemsolving.com/c/6/1/c61abf6a616a4e77aff1e5fa0614dd8dd08de19e.png)
![\[
f(x^2+y^2)=f(x^2)+f(y^2)+2f(x)f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/5/0/0/500bf3ccb32c571a892ac4e7d9456812b830267e.png)
![\[
f(x+y)f(x-y) = \Bigl(f(x)+f(y)\Bigr)^2 - 4x^2f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/0/5/e/05e255a75314cea6a36cd880deaea132e4382645.png)
such that![\[
f(1)=2,\quad f(2)=4,\quad \text{and}\quad f\bigl(f(m)+f(n)\bigr)=f\bigl(f(m)\bigr)+f(n) \quad \forall m,n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/2/7/b/27b250f26188d9ef6db7794da8508c4db1356109.png)
with 
,![\[
\Bigl(f(a)+f(b)\Bigr)\Bigl(f(c)+f(d)\Bigr)=(a+b)(c+d).
\]](http://latex.artofproblemsolving.com/9/c/e/9ce0e0b9b36a00f1b42093514a589cebfe61d4e7.png)
![\[
f(x^2)\Bigl(f(x)^2+f\Bigl(\frac{1}{y^2}\Bigr)\Bigr)=1+f\Bigl(\frac{1}{xy}\Bigr) \quad \forall x,y \in \mathbb{R}\setminus\{0\}.
\]](http://latex.artofproblemsolving.com/9/c/7/9c7521fdf0588fa1ae6eeeb5d74bb52f1e64b837.png)
![\[
f\bigl(f(x)-f(y)\bigr)=f\bigl(f(x)\bigr)-2x^2f(y)+f(y^2) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/5/e/3/5e3eea7bb9e355bce5b778334cb223788ea86ee8.png)
![\[
f(x+1)=f(x)+1 \quad \text{and} \quad f\Bigl(\frac{1}{f(x)}\Bigr)=\frac{1}{x} \quad \forall x \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/5/6/d/56d0628818830965dcfdb1602f6ec035be955db1.png)
![\[
f(x+f(x)f(y))=f(x)+x\,f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/2/b/8/2b872c86fe30002a8fde7c224dc2b51227fab595.png)
![\[
f(x)+f(y)-f(x+y)=xy \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/6/9/0/690d38473bf45b7d195abc59294c2c4d467161fe.png)
72. Find all functions ![\[
f(x^2+y^2) = f\bigl(f(x)\bigr) + f(xy) + f\bigl(f(y)\bigr) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/1/e/5/1e59855c293b79f49d5bd5feb3420ce8e25712fe.png)
![\[
(x+y)f\bigl(f(x)y\bigr) = x^2f\bigl(f(x)+f(y)\bigr) \quad \forall x,y \in \mathbb{R}^+.
\]](http://latex.artofproblemsolving.com/c/f/7/cf7fa80efdc6c430edbef5ae513095b719a00bfa.png)
![\[
f(x+y^2) \ge (y+1)f(x) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/7/9/a/79ac6ff22038cff644ce518d6099d6573fb25317.png)
![\[
f(x)f(y) \le f(xy) \quad \text{and} \quad f(x)+f(y) \le f(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/b/2/a/b2aaa0fd33bee04049fbefc5a6f927ca157b41c7.png)
such that![\[
\begin{aligned}
& f(x) \ge 0 \quad \forall x \in \mathbb{Q}, \quad f(x)=0 \iff x=0,\\[1mm]
& f(xy) = f(x) \cdot f(y),\\[1mm]
& f(x+y) \le \max\{f(x),f(y)\} \quad \forall x,y \in \mathbb{Q}.
\end{aligned}
\]](http://latex.artofproblemsolving.com/b/7/8/b78dcc69537812955d264c7fdcacba667305f83a.png)
![\[
xf(y) - yf(x) = f\Bigl(\frac{y}{x}\Bigr) \quad \forall x,y \in \mathbb{R} \text{ with } x \neq 0.
\]](http://latex.artofproblemsolving.com/3/0/4/304aa27b934df3d2caaa168a557cdfac9f7ab836.png)
![\[
\sum_{k=1}^{n} \frac{1}{f(k)\cdot f(k+1)} = \frac{f(f(n))}{f(n+1)} \quad \forall n \in \mathbb{N}.
\]](http://latex.artofproblemsolving.com/7/b/5/7b5e7541687ef9adc7ea0008de7abc06103b3557.png)
,![\[
(2m+1)f(n)f(2mn) = 2m f(n)^2 + f(2mn)^2 + (2m-1)^2 n.
\]](http://latex.artofproblemsolving.com/4/d/0/4d0cad56b852cc6132b7ecd550f53eeb27579430.png)
![\[
f(x - f(y)) = f\bigl(f(y)\bigr) - 2x f(y) + f(x) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/d/1/9/d19fdd05f61be9d5e5ec3a4c73c0606023193d9c.png)
![\[
f\bigl(f(x)-y^2\bigr) = f(x)^2 - 2f(x)y^2 + f(y^2) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/f/d/f/fdf5fafaca41d9eb815ef4d2755f522fff3f7385.png)
such that![\[
f\bigl(x+f(x)+2y\bigr) = 2x + f\bigl(2f(y)\bigr) \quad \forall x,y \in [0,+\infty).
\]](http://latex.artofproblemsolving.com/8/4/7/847f8467007bbe7d5340b024228acecc8da0e727.png)
![\[
f(x^2)+f(xy) = f(x)f(y) + yf(x) + x\,f(x+y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/2/a/8/2a8c358381de1fe00b2311c66c1174d6751fb426.png)
![\[
f\bigl(x+f(x)+2y\bigr) = 2x + 2f\bigl(f(y)\bigr) \quad \forall x,y \in \mathbb{Q}.
\]](http://latex.artofproblemsolving.com/a/6/0/a600eda2098b4e46dadd68aee3ff6367b3a7cbf0.png)
![\[
\begin{aligned}
& f\bigl(x+f(x)^2+y+f(2z)\bigr) = 2x - f(x) + f\bigl(f(f(y))\bigr) + 2f\bigl(f(z)\bigr) \quad \forall x,y,z \in \mathbb{R},\\[1mm]
& f\bigl(f(0)\bigr) = f(0).
\end{aligned}
\]](http://latex.artofproblemsolving.com/c/3/a/c3ac3bbaedea0f7f4a7aa3a7c3e398dbbbed2654.png)
![\[
\begin{aligned}
& f(x+f(y)) = f(x)f(y) \quad \forall x,y>0,\\[1mm]
& \text{there are at most finitely many } x \text{ with } f(x)=1.
\end{aligned}
\]](http://latex.artofproblemsolving.com/4/7/e/47e353db758b7994923ec4183d2ed0841f14b4ab.png)
such that for all 
,![\[
m f(n) + n f(m) = (m+n)f\bigl(m^2+n^2\bigr).
\]](http://latex.artofproblemsolving.com/9/f/4/9f476da9bd9ac43806fdd1523944e67167b46597.png)
such that![\[
f(xyz) = x f(x) + y f(y) + z f(z) \quad \forall x,y,z \in (0,1).
\]](http://latex.artofproblemsolving.com/d/c/9/dc99494cfaefec35b0d46095ba141675ab637d58.png)
satisfying![\[
f(x^3+y^3+z^3) = f(x)^3 + f(y)^3 + f(z)^3.
\]](http://latex.artofproblemsolving.com/5/b/3/5b39e78632880011ac518f24ae503f8512d29968.png)
that are defined and continuous on the interval 
and that satisfy the functional equation![\[
f(x+y)=\frac{f(x)+f(y)}{1-f(x)f(y)}
\]](http://latex.artofproblemsolving.com/6/1/b/61b7667f2867e214a3141b8bc3ae557d28de7a6a.png)
for all 
.![\[
f\bigl(x^n+2f(y)\bigr) = (f(x))^n + y + f(y) \quad \forall x,y \in \mathbb{R},\; n\in \mathbb{Z}_{\ge2}.
\]](http://latex.artofproblemsolving.com/b/a/f/bafcd9cc7d7c8d970d1454c3514a873cc86b3554.png)
![\[
f(x+y)f(x-y)=\Bigl(f(x)+f(y)\Bigr)^2-4x^2f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/4/2/c/42cf5273ae006fe34effc6ec26e6945b120e447b.png)
![\[
\Bigl(f(a)+f(b)\Bigr)\Bigl(f(c)+f(d)\Bigr) = (a+b)(c+d).
\]](http://latex.artofproblemsolving.com/8/2/b/82beacda2bc3a315aae0c6184380db7a3d8bfefb.png)
![\[
f\bigl(x+f(x)f(y)\bigr)=f(x)+x\,f(y) \quad \forall x,y \in \mathbb{R}.
\]](http://latex.artofproblemsolving.com/a/d/8/ad8e1a55a603018a1125218ce5bfac176b298c15.png)
Denote the number of divisors of 
as 
,
for the number of those divisors with 
.![\[
n \;=\; 2^f \,p_1^{r_1}\,p_2^{r_2}\,\dots\,q_1^{s_1}\,q_2^{s_2}\,\dots
\]](http://latex.artofproblemsolving.com/a/4/7/a475044d6ab24aafd755983e1a032f1ba60e34aa.png)
where 
and 
.
be the number of ways ![\[
r_2(n) \;=\; 0 \quad \text{if any of the exponents } s_j \text{ are odd.}
\]](http://latex.artofproblemsolving.com/6/9/e/69ed7d6f34edad1d7c6c43db34d5f01fecac26e7.png)
![\[
\text{If all } s_j \text{ are even, then }
r_2(n) \;=\; 4\bigl(d_1(n)\;-\;d_3(n)\bigr).
\]](http://latex.artofproblemsolving.com/e/2/b/e2b3062dd285bb074aed50da6742384379a34424.png)
Every positive integer 
,
,
,
,
such that![\[
n = a^2 + b^2 + c^2 + d^2.
\]](http://latex.artofproblemsolving.com/c/8/3/c83c79a16be18252904181a74d836d79383afaa5.png)
is defined as a pair of unit squares which share a vertex but do not share a side. For which pairs of integers 
can an 
rectangular grid of unit squares be tiled with cucumbers?
.
rows and 
.
rectangle and 
rectangle. By induction both can be filled using cucumbers and so can the whole rectangle. For the base case of 
many 
squares, which is possible since 
are odd. So there are 
squares. Each cucumber will fill 
squares and hence it cannot fill odd number of squares and hence we are done! 
.
.
number of blue squares. Each cucumber must occupy atleast one red and one blue square. Thus if the board is tiled using cucumbers then we get that number of red tiles 
number of blue tiles. A contradiction! 
of positive integers satisfying 
is an element of 
and 
(not necesarily distinct in S)
.
which gives 
is in the set 
be the largest odd number in the set. Then 
is in 
and is the least even element in the set after 
.
which is our original claim. 
is even 
(or else 
)
.
are prime and satisfy![\[\frac{p}{{p + 1}} + \frac{{q + 1}}{q} = \frac{{2n}}{{n + 2}}\]](http://latex.artofproblemsolving.com/7/3/5/735ec9416a654f40121021bdd1233ffa86e42495.png)
for some positive integer 
.
Ofcourse 
And expanding gives 
Ofcourse 
Since 
and 
.
can be 
.
.
work.
be a sequence of primes such that 
and for 
is the largest prime factor of 
. Prove that 
for any 
,
,
.
such that 
has its largest prime divisor as 
.
.
,
.
.
thus 
.
for some 
,
.
But 
,
denotes the largest expononent of 
be two natural numbers. When we divide 
by 
,
and the quotient 
Determine all pairs 
for which 
.
then the maximum value of 
will be 
.
.
.
. By Jacobi's two square theorem,
.
.
Thus, 
is a perfect square number.
.
.
is a perfect square too!
.
.
.
and 
and 
.
and 
.
.
primes such that these terms satisfy.
and 
are primes.
.
.
.
.
and 
is a prime hence 
.
.
.
and 
.
and 
are both primes.
which means that 
.
.
or 
,
.
.
i.e 
,
Thus, 
,![\[ \prod_{1 \leq i < j \leq n} \frac{a_i-a_j}{i-j} \in \mathbb{Z} .\]](http://latex.artofproblemsolving.com/4/3/0/4302b6638b7ebd13c28130e7a969c6284f4ad531.png)
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \geq v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right). \]](http://latex.artofproblemsolving.com/3/b/5/3b5f9deb6b391a9640fe8b64eeedc99d5461365f.png)
The divisibility immediately follows. Indeed, the problem statement is equivalent to showing that the quantity![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \]](http://latex.artofproblemsolving.com/4/d/d/4dd9b4d8d8e1c2a25d85f65cbcf7ae6c93494baf.png)
is minimised when 
for all 
.![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( a_i-a_j \right) = \sum_{k \geq 1} |A_{p^k}| .\]](http://latex.artofproblemsolving.com/a/b/0/ab0f0f9cb159fd1e74f090806a247af3a3618832.png)
We proceed by computing the size of each individual set 
.![\[ A_{(p^k, x)} = \left\{ a_i \mid a_i \equiv x \pmod{p^k} \right\} \]](http://latex.artofproblemsolving.com/4/4/d/44d0b55326b872421bba03c8d6a3cfbd6cd01cf4.png)
for 
.
partitions the set 
because modular congruence is an equivalence relation. Moreover, 
if and only if 
for some 
.![\[ |A_{p^k}| = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}|}{2} .\]](http://latex.artofproblemsolving.com/4/2/b/42bef1bec3b07afbf989781b632bb981634d5aae.png)
I claim that the above sum is minimised if there exists an integer 
for all ![\[ f(a_0, a_1, \dots, a_{p^k-1} )=\sum_{x=0}^{p^k-1} \binom{a_x}{2} \]](http://latex.artofproblemsolving.com/e/9/2/e92723c09356b1b4e16b7b31c9aa665c403a053f.png)
has minimal value at 
that does not satisfy the above claim. Then there exists 
such that 
.
and rewrite as
Then![\[ \binom{a_i-1}{2} + \binom{a_j+1}{2} < \binom{a_i}{2}+\binom{a_j}{2} .\]](http://latex.artofproblemsolving.com/c/a/4/ca43f8e5daed4c375e4074f6bb83a70fa9c3236e.png)
Finally, if we assume without loss of generality that 
we conclude![\[ f(a_0, a_1, \dots ,a_{p^k-1} ) > f(a_0, a_1, \dots , a_i-1, \dots, a_j+1, \dots, a_{p^k-1} ) \]](http://latex.artofproblemsolving.com/0/b/b/0bb27c918147a6c68f5a678dc2aa55a2f79bde46.png)
contradicting the minimality of 
.
is partitioned by the 
,![\[ |A_{(p^k,0)}|+|A_{(p^k,1)}|+\dots+|A_{(p^k,p^k-1)}|=n . \]](http://latex.artofproblemsolving.com/6/e/5/6e53d1469796e1ef9f30a2605911e2780d22681c.png)
We may say that 
.![\[ |A_{p^k}|=f \left( | A_{(p^k,0)}|, |A_{(p^k,1)}|, \dots, |A_{(p^k,p^k-1)}|\right) \geq r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2}. \]](http://latex.artofproblemsolving.com/9/e/a/9ead7efbb8cdeb6060c191544c535d9ba4b1f334.png)
It remains to show that this value is taken when 
and 
.![\[ |A_{(p^k,x)}|= \space
\begin{cases}\left\lfloor \frac{n}{p^k}\right\rfloor +1 &\text{ if } 0 \leq x \leq r \\
\left\lfloor \frac{n}{p^k}\right\rfloor & \text{ if } r < x \leq p^k-1.
\end{cases} \]](http://latex.artofproblemsolving.com/f/c/c/fcc79b5842c90c1046bc8cc68124c8d6e002c7ed.png)
Then![\[ |A_{p^k}^{\star}|=f \left( | A_{(p^k,0)}^{\star}|, |A_{(p^k,1)}^{\star}|, \dots, |A_{(p^k,p^k-1)}^{\star}|\right) = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}^{\star}|}{2} = r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2} \]](http://latex.artofproblemsolving.com/7/8/1/78194a51e45e422000a8a9bc5a335c348490b39a.png)
when 
.![\[ v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( i-j \right) = \sum_{k \geq 1} |A^{\star}_{p^k}|. \leq \sum_{k \geq 1} |A_{p^k}|= v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) ,\]](http://latex.artofproblemsolving.com/c/1/1/c11b062e0185af7cfb058d01beb910f3caf84c0e.png)
completing the proof.![[asy]
size(30cm);
pen[][] p={{red,yellow,green},
{magenta,orange,yellow},
{blue,red,orange}};
latticeshade(texpath("Happy New Year to all!"),p);
[/asy]](http://latex.artofproblemsolving.com/4/9/a/49ae2a4385a19f37aa576cebb6cd625d034ea63e.png)
,
and the median 
divide 
into three equal parts. If 
,
is?![[asy]
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */
import graph; size(10cm);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = -8.92, xmax = 8.92, ymin = -5.4, ymax = 5.4; /* image dimensions */
pen zzttqq = rgb(0.6,0.2,0);
draw((-3.26,3.82)--(-6.92,-1.34)--(6.76,-1.62)--cycle, linewidth(2) + zzttqq);
/* draw figures */
draw((-3.26,3.82)--(-6.92,-1.34), linewidth(2) + zzttqq);
draw((-6.92,-1.34)--(6.76,-1.62), linewidth(2) + zzttqq);
draw((6.76,-1.62)--(-3.26,3.82), linewidth(2) + zzttqq);
draw((xmin, 48.857142857142854*xmin + 163.0942857142857)--(xmax, 48.857142857142854*xmax + 163.0942857142857), linewidth(2)); /* line */
draw((-3.26,3.82)--(-0.08,-1.48), linewidth(2));
/* dots and labels */
dot((-3.26,3.82),dotstyle);
label("$A$", (-3.18,4.02), NE * labelscalefactor);
dot((-6.92,-1.34),dotstyle);
label("$B$", (-6.84,-1.14), NE * labelscalefactor);
dot((6.76,-1.62),dotstyle);
label("$C$", (6.84,-1.42), NE * labelscalefactor);
label("$c$", (-5.36,1.44), NE * labelscalefactor,zzttqq);
label("$a$", (-0.1,-1.78), NE * labelscalefactor,zzttqq);
label("$b$", (1.9,1.4), NE * labelscalefactor,zzttqq);
label("$f$", (-3.08,4.92), NE * labelscalefactor);
dot((-3.36710245870117,-1.4127201251143038),linewidth(4pt) + dotstyle);
label("$D$", (-3.28,-1.26), NE * labelscalefactor);
dot((-0.08,-1.48),linewidth(4pt) + dotstyle);
label("$E$", (0,-1.32), NE * labelscalefactor);
label("$g$", (-1.96,1.02), NE * labelscalefactor);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */
[/asy]](http://latex.artofproblemsolving.com/2/7/4/274d0dbc781e3bc128d6477a45f887b2ed13f17b.png)
.
as 
.
.
,
.
,
.
,
.
.
.
be the circumcenter, then 
,
,
are colinear. Therefore, 
or 
.
and 
coincide, and the angle is not trisected. Thus, 
is a right-angled triangle. Consequently, the altitude divides the 
angle into 
and 
,
,
.
of a triangle satisfy the relations 
and 
.
,
be a triangle in which 
.
,
to meet 
at 
and 
.
equals?
.
(Pythagorean Theorem). Thus 
and 
(Pythagorean Theorem).
be a square of side length 
be points in the interiors of the sides 
,
then find the length of ![[asy]
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */
import graph; size(10cm);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = -8.92, xmax = 8.92, ymin = -5.4, ymax = 5.4; /* image dimensions */
pen zzttqq = rgb(0.6,0.2,0);
draw((-3.58,2.26)--(-3.64,-3.22)--(1.84,-3.28)--(1.9,2.2)--cycle, linewidth(2) + zzttqq);
/* draw figures */
draw((-3.58,2.26)--(-3.64,-3.22), linewidth(2) + zzttqq);
draw((-3.64,-3.22)--(1.84,-3.28), linewidth(2) + zzttqq);
draw((1.84,-3.28)--(1.9,2.2), linewidth(2) + zzttqq);
draw((1.9,2.2)--(-3.58,2.26), linewidth(2) + zzttqq);
draw((-3.5946697742558436,0.9201606179663049)--(1.8594891123393478,-1.499994406339482), linewidth(2));
draw((xmin, 2.253640296517657*xmin + 0.49841400936201097)--(xmax, 2.253640296517657*xmax + 0.49841400936201097), linewidth(2)); /* line */
draw((0.760574548844643,2.2124754611440354)--(-1.6595804754611438,-3.2416834254511557), linewidth(2));
draw((xmin, -0.010948905109489145*xmin-1.47963503649635)--(xmax, -0.010948905109489145*xmax-1.47963503649635), linewidth(2)); /* line */
draw((xmin, 91.33333333333121*xmin + 148.3333333333298)--(xmax, 91.33333333333121*xmax + 148.3333333333298), linewidth(2)); /* line */
/* dots and labels */
dot((-3.58,2.26),dotstyle);
label("$A$", (-3.5,2.46), NE * labelscalefactor);
dot((-3.64,-3.22),dotstyle);
label("$B$", (-3.56,-3.02), NE * labelscalefactor);
dot((1.84,-3.28),dotstyle);
label("$C$", (1.92,-3.08), NE * labelscalefactor);
dot((1.9,2.2),dotstyle);
label("$D$", (1.98,2.4), NE * labelscalefactor);
dot((-3.5946697742558436,0.9201606179663049),dotstyle);
label("$E$", (-3.52,1.12), NE * labelscalefactor);
dot((1.8594891123393478,-1.499994406339482),dotstyle);
label("$F$", (1.94,-1.3), NE * labelscalefactor);
label("$j$", (-1,-0.58), NE * labelscalefactor);
dot((-1.6595804754611438,-3.2416834254511557),dotstyle);
label("$G$", (-1.58,-3.04), NE * labelscalefactor);
label("$k$", (1.74,4.92), NE * labelscalefactor);
dot((0.760574548844643,2.2124754611440354),linewidth(4pt) + dotstyle);
label("$H$", (0.84,2.38), NE * labelscalefactor);
label("$l$", (-0.76,-0.38), NE * labelscalefactor);
label("$m$", (-8.76,-1.22), NE * labelscalefactor);
label("$n$", (-1.42,4.92), NE * labelscalefactor);
dot((-1.5995804754611425,2.238316574548844),linewidth(4pt) + dotstyle);
label("$I$", (-1.52,2.4), NE * labelscalefactor);
dot((-3.620510887660651,-1.4399944063394812),linewidth(4pt) + dotstyle);
label("$J$", (-3.54,-1.28), NE * labelscalefactor);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */
[/asy]](http://latex.artofproblemsolving.com/c/8/c/c8c25eae8a34b902f4eb033642872f74f9afe087.png)
and 
.
as 
,
and 
.
.
be located in the 
p
,
(i).
,
(ii).
.
be a point inside a triangle 
.
and 
be the images of 
respectively. The distance between the circumcenters of triangles 
is?
and 
and 
.
then 
and 
.
is just 
.
is just 
.
.
and 
right angled triangle thus the circumradius is 
.
,
be midpoint of 
and 
be points on ray
and 
respectively such that 
.
be the radius of 
and 
be
.
where 
and 
.
and 
.
and 
.
.
or 
.
,
.
.
.
.
be a triangle in which 
and let 
be its in-centre. Suppose 
.
such that 
.
is isosceles.
.
and 
.
(as 
is isosceles.
is isosceles, 
which means that 
and 
.
.
.
is a cyclic quadrilateral.
which means that 
.
.
.
,
.
with radius 
contain 
respectively. Find 
.
be the midpoints of 
respectively. Let 
be the centres of 
Similarly, 
Using LoS, 
or 
.
.
.
places to choose form and 
.
be the number of people per car. What is the smallest value of 
,
.
.
is 
.
or 
.
and 
thus resulting the final 
.
was quite natural. Now the main thing is observing that 
satisfy the equation 
.
is bijective.
such that 
.
But a function can't give two distinct values, unless 
this is not true so 
,
To obtain any 
just let 
.
Thus 
which satisfy for all 
for 
![\[f(x)=x^2\cdot f\left(\frac{1}{x}\right)=x^2\cdot f\left(1+\frac{1-x}{x}\right)=x^2+x^2\cdot f\left(\frac{1-x}{x}\right)=x^2+x^2\cdot \frac{(1-x)^2}{x^2}\cdot f\left(\frac{x}{1-x}\right)=\]](http://latex.artofproblemsolving.com/4/d/a/4da809b44b08f413bde69c4df27874c14bc7e4b8.png)
![\[x^2+(1-x)^2\cdot f\left(\frac{1}{1-x}-1\right)=x^2+(1-x)^2\cdot f\left(\frac{1}{1-x}\right)-(1-x)^2=x^2-(1-x)^2+f(1-x)=2x+f(-x)=2x-f(x)\]](http://latex.artofproblemsolving.com/3/d/d/3ddf8024f0a68b7279bee29f51e58e913fd1d3aa.png)
and hence 
holds for all 
which easily extends to 
such that
and 
be the assertion 
and so 
and 
since 
is non constant;
and so :
and so 
implies 
which gives immediately 
,
and 
which indeed is a solution.
implies 
which gives immediately 
and 
and 
which indeed is a solution.
implies 
which gives immediately 
which indeed is a solution.
March 2025
February 2025