As Mr.Tuan said, for $(b)$ we can choose $n=p-1$ where $p \geq 7$. To prove part $(a)$ first observe that \begin{align*} a_{2n}&=\frac{1}{2n}\left(\left\lfloor\frac{2n}{1}\right\rfloor+\left\lfloor\frac{2n}{2}\right\rfloor+\cdots+\left\lfloor\frac{2n}{n}\right\rfloor+\left\lfloor\frac{2n}{n+1}\right\rfloor+\cdots+\left\lfloor\frac{2n}{2n}\right\rfloor \right)\\ &>\frac{1}{2n}\left(\left\lfloor\frac{2n}{1}\right\rfloor+\left\lfloor\frac{2n}{2}\right\rfloor+\cdots+\left\lfloor\frac{2n}{n}\right\rfloor\right)\\ & \geq \frac{1}{2n}\left(2\left\lfloor\frac{n}{1}\right\rfloor+2\left\lfloor\frac{n}{2}\right\rfloor+\cdots +2\left\lfloor\frac{n}{n}\right\rfloor\right)\\ &=\frac{1}{n}\left(\left\lfloor\frac{n}{1}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+\cdots+\left\lfloor\frac{n}{n}\right\rfloor\right)\\ &=a_{n} \end{align*}where we used the fact that $\lfloor 2x \rfloor \geq 2 \lfloor x \rfloor $ for any real number $x$. Now, suppose there exists only finitely many $n$ such that $a_{n+1}> a_n$ and let $m$ be largest such $n$ .Then $$a_{m+1}\geq a_{m+2}\geq a_{m+3} \geq \dots \geq a_{2m+2}$$which is a contradiction.

for part a) you can also put n= 2^k -1 for k big enough:dyou just use some easy analysis to prove that:D

bodom wrote: for part a) you can also put n= 2^k -1 for k big enough:dyou just use some easy analysis to prove that:D Please post concrete!

ok.sorry.let $ T_{m}$ be the number of natural divisors of $ m$.we have that $ na_{n}+T_{n+1}=(n+1)a_{n+1}$(*) so proving $ a_{n+1}>a_{n}$ <=> (using (*)) $ a_{n}< T_{n+1}$ <=>$ [n/1]+[n/2]+.....+[n/n] < nT_{n+1}$.put $ n=2^{k}-1$.we will prove that $ nT_{n+1}>n/1+n/2+....n/n >[n/1]+[n/2]+.....+[n/n]$ <=> $ T_{n+1}>1+1/2+1/3+...+1/n$.but $ n+1=2^{k}$,so $ T_{n+1}=k+1$.now let's prove $ k>1+1/2+1/3+....1/(2^{k})$ for k big enough.but using cesaro-stolz we get that$ lim[ (1+1/2+.....+1/2^{k})/k]=ln2$ and $ ln2<1$so our claim is now proved

You are true, i think so. But bodom wrote: $ lim[ (1+1/2+.....+1/2^{k})/k]=ln2$ It is wrong!

i don't see why it is so wrong.let$ a_{k}=1+1/2+1/3+1/4+.......+1/(2^{k}-1)+1/(2^{k})$and $ b_{k}=k$.but$ lim (a_{k+1}-a_{k})/(b_{k+1}-b_{k})=lim[1/(2^{k}+1)+1/(2^{k}+2)+.......+1/(2^{(}k+1) )]=ln2$ so using cesaro-stolz we have that $ lim a_{k}/b_{k}= ln2$.

Sorry, I mean that $ 1+\frac{1}{2}+\frac{1}{2^{2}}+...$ . I am wrong!

Or you can just prove by an easy induction on $ k$ that $ \tau(2^{k})=k+1 > \frac{1}1+\ldots+\frac1{2^{k}-1}$. Since we know that $ n(n+1)(a_{n+1}-a_{n})=n\tau(n+1)-\left(\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+\cdots+\left[\frac{n}{n}\right]\right) >n\tau(n+1)-n\left(\frac{1}{1}+\ldots+\frac{1}{n}\right)$, this would imply $ a_{2^{k}}> a_{2^{k}-1}$. The claim is true for $ k=1$. Then $ \sum_{i=1}^{2^{k+1}-1}\frac1i = \sum_{i=1}^{2^{k}-1}\frac1i+\sum_{i=2^{k}}^{2^{k+1}-1}\frac{1}{i}< k+1+\sum_{i=2^{k}}^{2^{k+1}-1}$ so it is enough to prove that $ \sum_{i=2^{k}}^{2^{k+1}-1}\leq 1$. This is true for $ k=1$. Then $ \sum_{i=2^{k+1}}^{2^{k+2}-1}= \sum_{i=2^{k}}^{2^{k+1}-1}\left(\frac{1}{2i}+\frac{1}{2i+1}\right)< \sum_{i=2^{k}}^{2^{k+1}-1}\frac1i \leq 1$. Done

Actually, it's not necessary to use a specific sequence like $ n = 2^{k}-1$. Since $ d(n)$ is unbounded, you can find infinitely many values of n such that $ d(n+1) > d(1), d(2),\ldots, d(n)$, and such an $ n$ does the job. Another way to treat (a): Assume the contrary. Then $ a_{n}$ has to be bounded above. But \[ a_{n}\geq\frac{1}{n}\left(\frac{n}{1}-1+\frac{n}{2}-1+\ldots+\frac{n}{n}-1\right) =\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n},\] which is known to diverge, contradiction.

mattilgale wrote: We define a sequence $ \left(a_{1},a_{2},a_{3},...\right)$ by setting \[ a_{n} = \frac {1}{n}\left(\left[\frac {n}{1}\right] + \left[\frac {n}{2}\right] + \cdots + \left[\frac {n}{n}\right]\right)\] for every positive integer $ n$. Hereby, for every real $ x$, we denote by $ \left[x\right]$ the integral part of $ x$ (this is the greatest integer which is $ \leq x$). a) Prove that there is an infinite number of positive integers $ n$ such that $ a_{n + 1} > a_{n}$. b) Prove that there is an infinite number of positive integers $ n$ such that $ a_{n + 1} < a_{n}$. First a lemma: $ \sum_{k=0}^{n+1} \left \lfloor \frac{n+1}{k} \right \rfloor - \left \lfloor \frac{n}{k} \right \rfloor = \tau(n+1)$, $ \tau(n)$ is the number of divisors of $ n$. The proof follows from the fact that $ \left \lfloor \frac{n+1}{k} \right \rfloor - \left \lfloor \frac{n}{k} \right \rfloor = 1 \iff k \mid n+1$. So: $ (n+1)(a_{n+1}-a_n) = \sum_{k=0}^{n+1} \left ( \left \lfloor \frac{n+1}{k} \right \rfloor - \left \lfloor \frac{n}{k} \right \rfloor \right )-\frac{1}{n} \sum_{k=0}^{n} \left \lfloor \frac{n}{k} \right \rfloor = \tau(n+1)-a_n$ Assume that for some $ N$ $ a_{n+1} \ge a_n$ for all $ n \ge N$. Then $ \tau(n+1) \ge a_n$, and $ 2 = \tau(p-1+1) \ge a_{p-1}$ for all primes and hence $ a_n \le 2$ for all $ n \ge N$. But $ a_n$ is unbounded. Contradiction. Assume that for some $ N$ $ a_{n+1} \le a_n$ for all $ n \ge N$. Then $ a_n$ is decreasing. But $ a_n$ is unbounded. Contradiction.

for part a , we can choose n+1=2^k

It is well known that $\displaystyle \sum_{i=1}^{n} \left \lfloor \dfrac{n}{i} \right \rfloor = \displaystyle \sum_{i=1}^{n} d(i)$ where $d(i)$ denotes the number of natural divisors of $i$ (see INMO 2014 P2). Now, \[a_{n+1} > a_n \iff n \displaystyle \sum_{i=1}^{n+1} d(i) > (n+1) \displaystyle \sum_{i=1}^{n} d(n) \\ \iff d(n+1) > \dfrac{1}{n}\displaystyle \sum_{i=1}^{n} d(i) = a_n.\] Similarly, $a_n < a_{n+1}$ iff $d(n+1) < a_n.$ For the first part, just let $n+1$ be a prime. For the second part, choose a $n$ such that $d(n+1) > d(i)$ for all $1 \leq i \leq n$ (if only finitely many such $n$ existed, there would exist a $k$ such that $d(i) < k$ for all $i \in \mathbb{N}$ which is obviously impossible because for any prime $p,$ $d(p^k) = k+1$).

For a) just notice that $a(2n)>a(n)$ and this is true cause $[2n/t]>=[n/t]+[n/t]$ so we are finished. For b),just pick $n=p-1$,where $p$ is a prime.Now,cause it is obvios that $[p/k]=[p-1/k]$,for all k non equal $p$ or $1$,so we just need $a(p-1)>2$ and this is true for all $p>=7$,so we are finished(there are infinitely many primes).

The problem is easy First observe that for all $k|n$ $\lfloor {\frac{n}{k}} \rfloor = \lfloor {\frac{n}{k-1}} \rfloor+1$, otherwise $\lfloor {\frac{n}{k}} \rfloor = \lfloor {\frac{n}{k-1}} \rfloor$ (a) $n=2^k-1$ (b)$n=p-1$ They quite easily satisfy the conditions

$na_n=\tau(n)+(n-1)a_{n-1}$. Therefore $n(a_{n+1}-a_n)=\tau(n+1)-a_{n+1}, |a_{n+1}-ln(n)|<1.$ When $n+1=p\ge 7$ - prime, then $\tau(p)=2<a_p\to a_p<a_{p-1}$. When $n+1$ had many divisors (for example n+1=k! or p#) $\tau(n+1)>ln(n)+1\to a_{n+1}>a_n$.

1) $a_n\geq \frac{1}{n}(\sum_{k=1}^{n}\frac{n}{k}-n) =\sum_{k=1}^{n}\frac{1}{k}-1$ Hence $\lim a_n = +\infty $ , in other words $a_n$ cannot be decreasing ...

http://www.artofproblemsolving.com/community/c42708h1063316_imo_2006_shortlist_n3 please take your time and check my solution

https://ibb.co/4tJNCQ4

a)Assume the opposite and proceed. Clearly this implies that the sequence is bounded. However $a_n=\sum_{i=1}^n \lfloor{\frac{n}{i}}\rfloor>\sum_{i=1}^n \frac{1}{i}-1$ which is unbounded a contradiction so we are done. b)Take $n=p-1$ and so it suffices to show $1+\sum_{k=1}^n (\lfloor{\frac{n+1}{k} \rfloor -\lfloor \frac{n}{k} }\rfloor)=1+\sum_{k \le n,k|n+1}<a_n$,as required(it implies $a_{p}>2$ so just choose $p$ to be large enough and since the sequence diverges we are done)

The first time I have succeeded in solving an N3 mattilgale wrote: We define a sequence $ \left(a_{1},a_{2},a_{3},\ldots \right)$ by \[ a_{n} = \frac {1}{n}\left(\left\lfloor\frac {n}{1}\right\rfloor + \left\lfloor\frac {n}{2}\right\rfloor + \cdots + \left\lfloor\frac {n}{n}\right\rfloor\right), \]where $\lfloor x\rfloor$ denotes the integer part of $x$. a) Prove that $a_{n+1}>a_n$ infinitely often. b) Prove that $a_{n+1}<a_n$ infinitely often. Proposed by Johan Meyer, South Africa LEMMA $$[\frac{n+1}{k}]-[\frac{n}{k}]=1(\text {if k divides n+1})=0(\text {otherwise})$$See that $$(n+1)a_{n+1}=n.a_n + d(n+1)$$We will prove part $b$ first CLAIM $1+\frac{1}{2}+\cdots \frac{1}{2^n}>\frac{n}{2}$ Proof: $$1+\frac{1}{2}>1$$$$\frac{1}{3}+\frac{1}{4}>\frac{1}{4}+\frac{1}{4}= \frac{1}{2}$$$$\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}>\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=\frac{1}{2}$$Similarly continuing with break at every power of $2$ and summing gives us the stated inequality. So there will exist some $N$ for which $\forall n\ge N$ $$1+\frac{1}{2}+\cdots \frac{1}{n}>3$$Or using $[x] >x-1$ , $$a_n>2$$Take $n+1$ to be a prime $>N$ Thus $$(n+1)a_{n+1}=n.a_n + 2>(n+1)a_n$$ Now part (a) Integrate the function $f(x)=\frac{1}{x}$ and get the inequality $$1+\frac{1}{2}+\cdots \frac{1}{n}< \ln(n+1)$$So using $[x]\leq x$, $$a_n\leq \ln(n+1) $$Also , $\forall k>1, 2^{k-1}>k$ Set $n+1=2^k$ Use $e>2$ and get $ \ln(2^k)<k$ and get $$a_n<d(n+1)\Rightarrow a_{n+1}>a_n$$

By counting in two ways the number of pairs $(a,b)$ with $a,b \le n$ and $a\mid b$, we get that \[a_n = \frac{1}{n}\sum_{i=1}^{n} d(i).\]a) Let $n+1$ be a highly composite number (a number such that for all $k<n+1$, $d(k)< d(n+1)$), of which there exists infinitely many positive integers, because $d(n)$ is unbounded. Then, since $d(n+1)$ is bigger than any preceding $d(k)$, it is bigger than their average, and hence its average with them must be bigger than their average, that is, $a_{n+1}>a_n$. b) Take $p\ge 11$ prime, $n=p-1$. Then, if $s = na_n$, \[s = d(1)+d(2)+d(3)+d(4)+d(5)+d(6) + \sum_{i = 7}^{p-1}d(i)\ge 1+2+2+3+2+4+\sum_{i = 7}^{p-1}d(i)>2p-2\]Hence, \[\frac{s}{p-1} > \frac{s+2}{p},\]i.e, $a_{n+1}<a_n$.

mattilgale wrote: We define a sequence $ \left(a_{1},a_{2},a_{3},\ldots \right)$ by \[ a_{n} = \frac {1}{n}\left(\left\lfloor\frac {n}{1}\right\rfloor + \left\lfloor\frac {n}{2}\right\rfloor + \cdots + \left\lfloor\frac {n}{n}\right\rfloor\right), \]where $\lfloor x\rfloor$ denotes the integer part of $x$. a) Prove that $a_{n+1}>a_n$ infinitely often. b) Prove that $a_{n+1}<a_n$ infinitely often. Proposed by Johan Meyer, South Africa Nice Problem. bit easy for N3 Btw here's how I thought, Posting it for storage. For any $n$ let $d(n)$ count the number of all divisors. Then we can easily see if $i\nmid n+1$ then $\lfloor \frac{n+1}{i}\rfloor =\lfloor \frac{n}{i}\rfloor $ and if $i|n+1$ then $\lfloor \frac{n+1}{i}\rfloor +1 =\lfloor \frac{n}{i}\rfloor $ Hence to get $a_{n+1}>\text{or} < a_n$ it's only the divisor points of $n+1$ which will make the difference. So clearly $\sum_{i=1}^{n+1} \lfloor \frac{n+1}{i}\rfloor =\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor +d(n+1)$ to get $a_{n+1}<a_n$ we must have $nd(n+1)<\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor$ the smallest possible value of $d(n+1)$ we can choose is $2$ So let's do that and if we get $2n<\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor$ which is true in fact we can get after some $n_0\in N$ we have $2n<n+\frac{n}{2}+\frac{n}{3}+\frac{n}{4}-3<\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor$ $\forall n\geq n_0$ Hence for $(b)$ if we take $n+1=\text{prime}$, we are done as there are infinitely many primes. Now we are left to prove $a_{n+1}>a_{n}$ also holds for infinitely many $n$ so we need $nd(n+1)>\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor$ but wait isn't $b_n=\sum_{i=1}^{n} \frac{1}{i}$ is just a big motivation to use cauchy Condensation bound i.e we always have $\sum_{k=0}^{m} 2^{k}\frac{1}{2^{k}}>b_{2^m}$ which can be proven easily by just using the fact $\frac{1}{n}$ is decreasing. Hence if we choose $n+1=2^m$ then we get that $d(n+1)=m+1$ and $m+1>b_{2^m}>b_{2^{m}-1}>\frac{\sum_{i=1}^{2^m-1} \lfloor \frac{2^m-1}{i}\rfloor}{2^m-1}$ Hence as $\sum_{i=1}^{2^m} \lfloor \frac{2^m}{i}\rfloor =\sum_{i=1}^{2^m-1} \lfloor \frac{2^m-1}{i}\rfloor +m+1$ So $a_{2^m}>a_{2^m-1}$

First, define $d(n)$ as the number of positive divisors of $n$. We note that $\left\lfloor\frac {n}{k}\right\rfloor$ is the number of positive multiples of $k$ less than or equal to $n$, so summing these over $k=1$ to $k=n$ is also just the sum of the number of divisors of each positive integer less than or equal to $n$. This means that $$a_n=\frac1n\sum_{k=1}^{n}d(k).$$It is now clear that part (a) happens for $n+1$ being highly composite(well known that there are infinitely many $n$ that does this), and part (b) happens for $n+1$ being every prime greater than or equal to $7$(also clear that there are infinitely many $n$ that does this).

It is well known that $$\sum_{i=1}^{n}\left \lfloor \frac{n}{i}\right \rfloor = \sum_{i=1}^{n}\tau(i),$$for positive integers $n \geq 1$ (which can be proven by considering $n\rightarrow n+1$ and noticing only divisors of $n+1$ get affected). We will use this many times throughout our proof. Note that $$na_n = \left \lfloor \frac{n}{1}\right \rfloor + \left \lfloor \frac{n}{2}\right \rfloor + \cdots + \left \lfloor \frac{n}{n}\right \rfloor = \sum_{i=1}^{n}\tau(i)$$and $$(n+1)a_{n+1} = \left \lfloor \frac{n+1}{1} \right \rfloor + \left \lfloor \frac{n+1}{2}\right \rfloor + \cdots + \left \lfloor \frac{n+1}{n+1}\right \rfloor = \sum_{i=1}^{n+1}\tau(i),$$so $$(n+1)a_{n+1} - na_n = \tau(n+1).$$We will use this to prove both parts. Part a): Assume for the sake of contradiction that $a_{n+1} > a_n$ finitely often. Then, there exists a positive integer $N$ such that for all $n > N$, we have $a_{n+1} < a_n$ (equivalently $a_{n+1} < a_n$ for sufficiently large $n$). Then, for all $n > N$, we have $$a_n = (n+1)a_n - na_n > (n+1)a_{n+1} - na_n = \tau(n+1).$$Now, take an integer $n > N$ such that $n+1$ has more divisors than any of $1, 2, \cdots, n$. This $n$ exists since if it did not, $\max(\tau(1), \tau(2), \cdots, \tau(n+1))$ would be bounded for all $n$, so $\tau(n)$ would always be bounded, which is clearly false (taking $n = 2^k$ gives $\tau(n) = k+1$ which can grow arbitrarily large). Then, for this particular $n$, $$n\tau(n+1) < na_n = \left \lfloor \frac{n}{1}\right \rfloor + \cdots + \left \lfloor \frac{n}{n}\right \rfloor = \tau(1) + \tau(2) + \cdots + \tau(n) < \underbrace{\tau(n+1) + \tau(n+1) + \cdots + \tau(n+1)}_{n \text{ times}} = n\tau(n+1),$$a contradiction, as desired. Part b): Assume for the sake of contradiction that $a_{n+1} < a_n$ finitely often. Then, there exists a positive integer $N$ such that for all $n > N$, we have $a_{n+1} > a_n$ (equivalently $a_{n+1} > a_n$ for sufficiently large $n$). Then, for all $n > N$, we have $$a_n = (n+1)a_n - na_n < (n+1)a_{n+1} - na_n = \tau(n+1).$$Now, take $n = p-1$, where $p > \max(49, N+1)$ is a prime. Then, $a_{p-1} < \tau(p) = 2$. Thus, $$2(p-1) > (p-1)a_{p-1} = \left \lfloor \frac{p-1}{1}\right \rfloor + \cdots + \left \lfloor \frac{p-1}{p-1}\right \rfloor \geq \left \lfloor \frac{p-1}{1}\right \rfloor + \left \lfloor \frac{p-1}{2}\right \rfloor + \left \lfloor \frac{p-1}{3}\right \rfloor + \left \lfloor \frac{p-1}{4}\right \rfloor.$$Note that $\left\lfloor \frac{a}{b}\right\rfloor = \frac{a}{b} - \left \{ \frac{a}{b}\right \} \geq \frac{a}{b} - 1,$ so $$2(p-1) > \frac{p-1}{1} + \frac{p-1}{2} + \frac{p-1}{3} + \frac{p-1}{4} - 4 = \frac{25}{12}(p-1) - 4 \iff 4 > \frac{1}{12}(p-1)\iff 48 > p-1 > 49 -1 = 48,$$a contradiction, as desired.

I really like this problem, as it uses two very neat key observations.

Set $$na_n=f(n)=\sum_{i=1}^{n} \lfloor \dfrac{n}{i} \rfloor $$and $f(0)=0.$ Then we have $f(n)-f(n-1)=\tau (n)$ and hence $a_n= \tfrac{\tau (1)+\dots +\tau (n)}{n}.$ Clearly $a_n > \tau (n+1)$ for $n+1$ prime, which proves $(a).$ And $(b)$ otherwise.

Since $\sum_{j=1}^m\left\lfloor\frac{m}{j}\right\rfloor=\sum_{j=1}^m\tau(j)$ and $\sum_{j=1}^m\left\lfloor\frac{m}{j}\right\rfloor-\left\lfloor\frac{m-1}{j}\right\rfloor=\tau(m),$ we see \begin{align*}a_{n+1}-a_n&=\frac{1}{n+1}\sum_{i=1}^{n+1}\left\lfloor\frac{n+1}{i}\right\rfloor-\frac{1}{n}\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\\&=\frac{1}{n(n+1)}\left(n\left(\sum_{i=1}^{n+1}\left\lfloor\frac{n+1}{i}\right\rfloor-\left\lfloor\frac{n}{i}\right\rfloor\right)-\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\right)\\&=\frac{1}{n(n+1)}\left(n\tau(n+1)-\sum_{i=1}^n\tau(i)\right).\end{align*}If $n+1$ is prime and $n\ge 6,$ then $$\sum_{i=1}^n\tau(i)=1+2+2+3+2+4+\sum_{i=7}^n\tau(i)>2n>n\tau(n+1)$$since $\tau(m)\ge 2$ if $m>1.$ This shows (b). Then, we claim by induction that there exist infinite $n$ such that $\tau(n+1)>\tau(i)$ for $1\le i\le n,$ which would prove (a). For our base case, take $n=5,$ noting we have $\tau(6)>\tau(i)$ for $1\le i\le 5.$ For the inductive step, suppose $\tau(k+1)>\tau(i)$ for $1\le i\le k.$ Then, choose the smallest $\ell$ such that $\ell>k+1$ and $\tau(\ell)>\tau(k+1).$ Clearly $\ell$ must exist since $\tau(m)$ can grow arbitrarily large. Then, $n=\ell-1$ works and our induction is complete. $\square$

Note that \[\frac {1}{n}\left(\left\lfloor\frac {n}{1}\right\rfloor + \left\lfloor\frac {n}{2}\right\rfloor + \cdots + \left\lfloor\frac {n}{n}\right\rfloor\right)=\frac1n (\tau(1)+\tau(2)+\dots+\tau(n))\]which means that $a_{n+1}>a_n$ if and only if $n\tau(n+1)>\tau(1)+\tau(2)+\dots+\tau(n)$ and $a_{n+1}<a_n$ if the inequality is flipped. Since $\tau$ function is unbounded, there must be infinitely many times when $\tau(n+1)>\tau(1),\dots,\tau(n)$ and $a_{n+1} > a_n$ in this case, and since $\tau(p)=2$, for all large enough primes, $a_{p}<a_{p-1}$.

We have the equivalence \[a_n=\frac{\tau(1)+\tau(2)+\dots+\tau(n)}{n}\]and now by the unboundedness of $\tau$ and the fact that primes have $2$ factors (which is the minimum, other than $1$), we are done with both parts. $\blacksquare$

Note that \[\frac {1}{n}\left(\left\lfloor\frac {n}{1}\right\rfloor + \left\lfloor\frac {n}{2}\right\rfloor + \cdots + \left\lfloor\frac {n}{n}\right\rfloor\right)=\frac1n (\tau(1)+\tau(2)+\dots+\tau(n))\]from an elementary divisor counting argument. Thus, $a_{n+1}>a_n$ if and only if $n\tau(n+1)>\tau(1)+\tau(2)+\dots+\tau(n)$. By the unboundedness of $\tau$, there are infinitely many $n$ with $\tau(n+1)>\max\{\tau(1),\ldots,\tau(n)\}$, so $a_{n+1}>a_n$ for infinitely many $n$. Also, $a_{n+1}<a_n$ if and only if $n\tau(n+1)<\tau(1)+\tau(2)+\dots+\tau(n)$; choosing sufficiently large $n$ such that $n+1$ is prime completes part (b). We are done.

The following claim trivializes the problem: Claim: \[a_n = \frac{\sum_{a=1}^n \tau(a)}{n},\]where $\tau(n)$ is the divisor function. Proof: Note that $\left\lfloor\frac{n}{1}\right\rfloor$ counts the number of multiples of $1$ up to $n$, $\left\lfloor\frac{n}{2}\right\rfloor$ counts the number of multiples of $2$ less than $n$, etc. Therefore, for some number $1 \geq k \geq n$, each divisor $d$ of $k$ is counted once once and only once, in the term $\left\lfloor\frac{n}{d}\right\rfloor$. By this argument for all $k$, we obtain that \[ \sum_{a=1}^n \tau(a) = \sum_{a=1}^n \left\lfloor\frac{n}{a}\right\rfloor,\]from which the claim easily follows. Now the result is clear - for part a) take some number $n$ such that $\tau(n+1) > \tau(1), \tau(2), ... \tau(n)$, and for part b) take $n = p-1$ for a prime $p$. It is easy to see with our claim that this works.

It is obvious to see that \[ a_n = \frac 1n \sum_{i=1}^n d(n) \]a) It remains to find $n$ such that \[ d(n+1) > \frac{\displaystyle\sum_{i=1}^n d(n)}{n} \]Let $n+1$ be a highly composite number, this finishes. b) We claim primes minus 1 that are $1$ mod $6$ work (an infinite number of these exist by Dirichlet). It remains to show that $\frac{a_{p-1}+2}{p} < \frac{a_{p-1}}{p-1}$ or $a_{p-1} > 2p-2$. If $ 6\mid p-1$, then $a_{p-1} > \frac{p-1}{1}+\frac{p-1}{2}+\frac{p-1}{3} + \frac{p-1}6 = 2(p-1)$, as desired.

storage from a while ago It's easy to see that $a_n=\frac{\sum d_i}{n}$ where d is the divisor function (for 1s, it's a factor floor[n/1] times, then 2s its a factor [n/2] times etc.). Then, for part b) take an odd prime p, which works since the sum in numerator increases only by 1 (from p/p) but denominator is also increased by 1, so it goes to $\frac{x+1}{y+1}<\frac{x}{y}\text{ }\forall x>y$. For part a), there are infinitely many times where $d(n+1)>d(1),d(2),\dots,d(n)$, which suffices because this implies $n(d(1)+d(2)+\dots+d(n+1))>(n+1)(d(1)+\dots+d(n))$, and dividing on both sides by n(n+1) finishes. $\blacksquare$