I think I know what the answer is, but I have no proof. By checking a lot of numbers with Mathematica (I couldn't have done that during the contest, of course ), it looks like the only numbers $n$ s.t. $3|P(n)$ are $2,\ 7,\ 22$. Strange set of solutions, huh? Maybe the fact that there are no more has something to do with (a) and with the fact that $7=3\cdot 2+1,\ 22=3\cdot 7+1,\ 67=3\cdot 22+1$. I have no clue about this, but maybe these are important observations.

What is Mathematica? _______________ "Our days are never coming back... " (Highway Song -> System of a down)

I agree with you, grobber. Define S[n] the residues mod 3^n and coprime to it. then for every a there is a' s.t.aa'/3^n=1(mod 3^n) Also if 3^k|a, define a' s.t. aa'/3^(n-k)=1(mod 3^(n-k)). Suppose 3^k<n<3^(k+1) we must have sum a' (a=1..n) divisible by 3^(k+1) (*) We group 1..n into A[1]..A[k] by the power of 3 dividing them By (*) we must have 3|sum(a') ai n A[k]. Hence both 3^k and 2*3^k belong to A[k]. So 2*3^k<=n.(1) If we have k=1 then this yields n=2. Now consider A[k-1] By (1) we can show 1,2,4,5 belong to A[k-1] and maybe 7 or 7, 8. But we use (*) and (1) to get 3|sum(a') a' in A[k-1] + 1. Checking we get just 7 belong to A[k-1]. So 7*3^(k-2)<=n<8*3^k-2. If k=0 we get n=7. Continuing like this we get 22/27<=n<23/27 yielding n=22 for k=3. But this procedure gives no solution further (we have 2 possible residues to choose, and the desired residue in luckily not among them). Hence we stuck and we get grobber's result. I know my solution is hard to understand. Sorry I can't explain it. To solve it you must draw the tables of a' for S[1],S[2],S[3],S[4]. 81 numbers. Elegant, huh? If this is the only solution they've got, this is a horrible problem. Maybe it involves a beatiful idea, but counting 81 numbers..

iura wrote: I agree with you, grobber. [...] If this is the only solution they've got, this is a horrible problem. Maybe it involves a beatcan someone explain it because I can't understand it?please write the thought and the conclusion. iful idea, but counting 81 numbers.. can someone explain it because I can't understand it?please write the thought and the conclusion. I also have a thought.for P(k) is not divisiable by 3,we can prove P(3k),P(3k+1),P(3k+2) is not ,either.

I think I have found a much easier solution: $\displaystyle 1+\frac 12+ \cdots + \frac 1n$ = $\displaystyle \frac { \sum^{n}_{j=1} \frac{n!}{j}} {n!} $ Take the greatest dividing exponent $a$ such that $3^a$ || $n!$, which means that $3^a$ divides $n!$, but $3^{a+1}$ does not divide it. For $n \geq 27$ the greatest dividing exponent of $\sum^{n}_{j=1} \frac{n!}{j}$ is less than $a$. 1) $\displaystyle 3^b \leq n \leq 2*3^b-1$ For $1 \leq j \leq n$, $j$ $\neq$ $3^b$, then $3^{a-b+1}$ | $\frac{n!}{j}$. But $3^{a-b}$ || $\frac{n!}{3^b}$, so $3^{a-b}$ || $\sum^{n}_{j=1} \frac{n!}{j}$, done. 2) $\displaystyle 2*3^b \leq n \leq 3^{b+1}-1$ For $1 \leq j \leq n$, $j$ $\neq$ $3^{b-1}$, $2*3^{b-1}$, $3^b$, $4*3^{b-1}$, $5*3^{b-1}$, $2*3^b$, and eventually $7*3^{b-1}$, $8*3^{b-1}$, then $3^{a-b+2}$ | $\frac{n!}{j}$. But $\displaystyle 3^{a-b+1}$ || $\displaystyle \frac{n!}{3^{b-1}} + \frac{n!}{2*3^{b-1}} + \frac{n!}{3^b} + \frac{n!}{4*3^{b-1}} + \frac{n!}{5*3^{b-1}} + \frac{n!}{2*3^b}$ = $\displaystyle \frac{49n!}{20*3^{b-1}} $. Consider each subcase: 2.1) $\displaystyle 2*3^b \leq 7*3^{b-1} - 1 $ $3^{a-b+1}$ || $\displaystyle \frac{49n!}{20*3^{b-1}} $ , done. 2.2) $\displaystyle 7*3^{b-1} \leq 8*3^{b-1} - 1$ $3^{a-b+2}$ || $\displaystyle \frac{363n!}{140*3^{b-1}} $ This case is again subdivided and consider $j$ such that $3^{a-b+3}$ | $\frac{n!}{j}$ while for the others give: $3^{a-b+2}$ || $\sum^{n}_{j=1} \frac{n!}{j}$, that's why we must have $ b \geq 3 $. 2.3) $\displaystyle 8*3^{b-1} \leq 3^{b+1} - 1$ $3^{a-b+1}$ || $\displaystyle \frac{761n!}{280*3^{b-1}} $ , done. I have overviewed it and I think it is quite wrong, but I will not delete it anyway.

well,I think your solution are right and beautiful.but we have to check n from 1 to 26.I think it will also be a huge work.if anyone in the test could do this work?

@heartwork: I like your approach very much. Your response is a bit hard to understand, but if I understand correctly, the only case we have to worry about is when $7*2^{b-1}\le n<8*2^{b-1}$. As you noted, we again need to take subcases, i.e by considering the numbers of the form $3^{b-2}, 2*3^{b-2},...26*3^{b-2}$. But this seems tedious, and how do you know you won't have to take subcases again. Can anyone fill in the details here?

Using $3$-adic valuation is good! For a rational number $x$, as usual with $\nu_3(x)$ we denote the largest (possibly negative) integer $k$ such that $\frac{x}{3^k}$ is an integer. Note the key property $\nu_3(A+B) \geq \min(\nu_3(A),\nu_3(B))$ with equality if $\nu_3(A) \neq \nu_3(B)$. Let $S_n = \sum_{i=1}^n \frac{1}{i}$. Then $S_{3n} = \frac{1}{3}S_n + \sum_{i=1, 3\nmid i}^{3n} \frac{1}{i} = \frac{S_n}{3} + \frac{a_n}{b_n} = \frac{S_nb_n + 3a_n}{3b_n}$ where $b_n$ is an integer which is not a multiple of $3$ and $a_n$ is a multiple of $3$ (the latter since $1/i \equiv i \pmod 3$ for $3\nmid i$ since $i^2 \equiv 1 \pmod 3$). Hence $1 + \nu_3(S_{3n}) = \nu_3(3S_nb_n) = \nu_3(S_nb_n + 3a_n)$ and so if the numerator of $S_n$ is not divisible by $9$ (meaning $\nu_3(S_n) \leq 1$), then $9\mid 3a_n$ and the above key property yield $1+\nu_3(S_{3n}) = \nu_3(S_{n})$; in particular, the numerator of $S_{3n}$ would not be divisible by $3$. Analogously, if the numerator of $S_n$ is not divisible by $9$ (meaning $\nu_3(S_n) \leq 1$), then $1+\nu_3(S_{3n+2}) = \nu_3(S_{n})$ and so the numerator of $S_{3n+2}$ would not be divisible by $3$; and if the numerator of $S_n$ is not divisible by $3$ (meaning $\nu_3(S_n) \leq 0$), then $1+\nu(S_{3n+1}) = \nu_3(S_{n})$ and so the numerator of $S_{3n+1}$ would also not be divisible by $3$. Now all that is remaining is annoying numerical calculations. For simplicity, call a number $n$ "bad" if the numerator of $S_n$ is not divisible by $3$ and "good" otherwise. By above we have the key inductive statement that if $n$ is bad, then so are $3n$, $3n+1$ and $3n+2$. Since $S_1 = 1$, $S_2 = \frac{3}{2}$, $S_3 = \frac{11}{6}$, $S_4 = \frac{25}{12}$, $S_5 = \frac{137}{60}$, $S_6 = \frac{147}{60} $, $S_7 = \frac{363}{140}$, $S_8 = \frac{761}{280}$ we see that $2$ and $7$ are good, $1$, $3$, $4$, $5$, $6$ and $8$ are bad and now we easily obtain that $9,\ldots,20$ are also bad. An unpleasant calculation (by using the above recursion between $S_{3n+1}$ and $S_n$) shows that $22$ is good (with numerator not divisible by $9$, hence $66$ and $68$ are bad) but $67$ is bad (and similar calculations yield that $21$ and $23$ are bad) and now a straightforward induction confirms that all other numbers are bad. Therefore the only solutions are $n=2,7,22$.