Let $f_\nu(a,b)=a\lceil b\nu\rceil-b\lfloor a\nu\rfloor$. Let $v=\nu$ because laziness. Also let $f=f_v$. Lemma 1: If $f(a,b)=k$, then either $f(a+b,b)=k+b$ and $f(a,a+b)=k$, or $f(a+b,b)=k$ and $f(a,a+b)=k+a$. Proof: Note that $\lfloor av+bv\rfloor\leq \lceil bv\rceil+\lfloor av\rfloor\leq \lceil av+bv\rceil$. Since they are all integers and the difference betw the first and 3rd term is 1, exactly one of the 2 inequalities is equality, while the other is off by 1. WLOG (the other case is similar) $\lfloor av+bv\rfloor=\lceil bv\rceil+\lfloor av\rfloor=\lceil av+bv\rceil-1$, then expanding $f$ gives $f(a+b,b)=k$ and $f(a,a+b)=k+a$, and we are done. Now we shall show that the number of excellent coprime pairs is $m$, and we are done, since $f(da,db)=da\lceil b(dv)\rceil-db\lfloor a(dv)\rfloor=df_{dv}(a,b)$. Let there be a whiteboard, and we write the pair $(1,1)$. At each turn, we pick any pair $(a,b)$ and replace it with $(a+b,b)$ and $(a,a+b)$. Give each pair $(a,b)$ a score of, wait for it, $\frac{x^{f(a,b)}}{(1-x^a)(1-x^b)}$. Expressing it as a polynomial, we get $x^{f(a,b)}(1+x^a+x^{2a}+...+x^b+x^{b+a}+x^{b+2a}+...+x^{2b}+...)$, with the coefficient of $x^{f(a,b)+k}$ is the number of ways to express $k$ as a sum of $a$'s and $b$'s. In particular, the score of $(1,1)$ is $x+2x^2+3x^3+...$. Note that the coefficients are always non-negative and the coefficient of the smallest power is always 1. By our lemma, it is easy to show that with each replacement, the total score does not change. Note that if we do the replacement "to infinity", we would have written down every coprime pair (and maybe erase it). Also the number of excellent pairs is the number of $m$'s after we $f$ every pair on the whiteboard after "infinity" replacements. This seems like the number of excellent pairs is the coefficient of $x^m$ in our total score which is $m$, but the infinity part is a bit iffy. To make it more rigorous, we need another lemma: Lemma 2: $\lim_{a\rightarrow\infty}f(a,b)=\infty$ for any fixed $b$. (and of course when $b\rightarrow\infty$ when $a$ is fixed) Proof: Write it as $f(a,b)=a(\lceil bv\rceil-bv)+b(av-\lfloor av\rfloor)$, and it becomes clear since $\lceil bv\rceil-bv>0$ is fixed and $av-\lfloor av\rfloor>0$. Now we keep replacing $(a,b)$ on the whiteboard whenever $a\leq m$ or $b\leq m$, and $f(a,b)\leq m$. This process will stop because of lemma 2. So now if $(a,b)$ is on the board with $a\leq m$ or $b\leq m$, the lowest power of the score of $(a,b)$ is more than $m$, and if $a,b>m$, the second lowest power of the score is also more than $m$. In other words, no matter how much more we replace, the number of pairs whose $f$ value equals $m$ will never increase and always remain the same. Thus that number of pairs is the number of excellent pairs, which is $m$, the coeffient of $x^m$ in total score, and we are done. Phew

The goal of this post is not necessarily to give the most elegant solution, but rather to present a fully motivated outline (which may or may not have a more conceptual rewording---I may eventually add in computations/details in hide tags), and perhaps along the way, shed some light on how one might come up with the problem (or maybe more realistically, just give some more context/story behind the problem). FWIW (and I might incorporate this in a handout someday), I think the problem has a very similar flavor to Farey fractions and USA TSTST 2013.2.

Aside: corollary of Step 6. Summing the lengths of the intervals, we have $m = \sum_{\substack{(a,b) = 1 \\ 1\le a,b\le m \\ a+b \ge m+1}} \frac{m}{ab}$. (This was actually a MOP test problem, which can easily be proven by induction---but I'm not sure where it came from originally!) Comment on the previous aside/food for thought. Using oneplusone's wonderful generating function observation, we have $\frac{x}{(1-x)^2} = \sum_{\substack{(a,b) = 1 \\ 1\le a,b\le m \\ a+b \ge m+1}} \frac{x^{f(a,b)}}{(1-x^a)(1-x^b)}$. (Starting with $(1,1)$, we replace $(r,s)$ with $(r+s,s)$ and $(r,s+r)$ whenever $r,s,r+s\le m$. Note that we preserve all $r,s\le m$ until the process terminates.) Then amusingly, multiplying by $(1-x)^2$ and plugging in $x=1$ gives the aside. (This also inspires a nice solution to the aside, using the identity $\frac{1}{rs} = \frac{1}{(r+s)s} + \frac{1}{r(s+r)}$, and again starting from $\frac{1}{1\cdot1}$, etc.) Comment on the location of (coprime) excellent pairs $(a,b)$. Analyzing Step 4 more closely, we see that if $(a,b)$ is excellent, then it has a unique predecessor ("can be traced back uniquely to") some $(a_0,b_0)$ with $a_0,b_0\le m$ and $a_0+b_0 \ge m+1$. Indeed, by the impossibility of Case 4.0 we must have one of $a,b \le m$, so either $a_0 = a$ or $b_0 = b$, i.e. the tracing back involved only one step (of division in the Euclidean algorithm). Also, we showed that in the doubly-infinite chain \[ \ldots,(a_0,b_0+2a_0),(a_0,b_0+a_0),(a_0,b_0),(a_0+b_0,b_0),(a_0+2b_0,b_0),\ldots, \] there's at most one excellent pair. It follows that $(a,b)$ is "immediate neighbor"-excellent (the given definition of excellent) if and only if it's "all predecessor"-excellent (a different but a priori more natural definition of excellence, where $(a,b)$ is good but all of its predecessors must not be good). Of course, with the $f(a,b)$ interpretation and oneplusone's Lemma 1, this is really easy to prove by nondecreasing stuffs. So maybe that's the drawback of my solution---it's easy to find but the details are somewhat unfortunate.

Was your proofs hard to think of? How do you come up with your proofs?

MathPanda1 wrote: How do you come up with your proofs? My solution above is a "no magic" solution---I think it's beautiful how everything works out, but overall it's pretty systematic. If you have questions about a specific part of the proof I can give a better answer. oneplusone's solution is a bit more inspired, but in retrospect the generating function/tree structure invariant is not so unfamiliar:

After playing around for a long time, lemma 1 is discovered. The proof is not hard, but noticing it is difficult. Then you start to suspect that lemma 1 is sufficient for proving the whole problem, with a little help from lemma 2. Now with lemma 1 and the aim of the problem, it is natural to think of the tree structure $(a,b)\to (a,b+a),(a+b,b)$. Now in order to prove $(1,1)$ will generate exactly $m$ children of $f$-value $m$, we need to generalize it to $(a,b)$. Experimenting for a while we will notice that the number of children with value $m$ is exactly the number of ways to sum numbers $a$ and $b$ to $m$ ($ia+jb=m$). Then we can just induct and we are done. BUT there is a problem, the tree is infinite and there is no base case. Now it gets annoying. Since we want to somehow 'store' the number of children of value $m$, and we already know how to get that number, generating functions come to mind. With generating function it is easy to generate the number of ways to sum $a$ and $b$ to $m$. The rest is just working out details.

Here is my write-up of the solution (I did not come up with this, and it's equivalent to oneplusone's solution and the official shortlist one, but it took me a long time to really understand). It suffices to show for any $\nu$ that the number of excellent pairs with $\gcd(a,b) = 1$ is $m$. Thus we henceforth fix $\nu$ and always assume $\gcd(a,b) = 1$. Let $f(a,b) = a \left\lceil b \nu \right\rceil - b \left\lfloor a \nu \right\rfloor$. We then consider the usual rooted binary tree given by the Euclidean algorithm, and label its vertices with the value of $f$. An $m$-good pair corresponds to a vertex $w = (a,b)$ with $f(w) = m$; it is $m$-excellent if the parent is not also labeled $m$. An example of one such tree is given below, with excellent vertices highlighted in color (I don't know if this actually corresponds to any $\nu$, but it is for illustration only). [asy][asy] size(11cm); pair leaf(pair E, int l, pen p, pair P) { dot("$"+(string)l+"$", P, dir(90), p+fontsize(10pt)); label("$"+(string)E+"$", P, dir(-90), black+fontsize(5pt)); return P; } pen edge = opacity(0.7)+dotted; draw((-4,3)--(0,4.5)--(4,3), edge); draw((-6,1.5)--(-4,3)--(-2,1.5), edge); draw((6,1.5)--(4,3)--(2,1.5), edge); for (int i=0;i<=3; ++i) { draw((4*i-7,0)--(4*i-6,1.5)--(4*i-5,0), edge); } draw((-7.5,-1)--(-7,0)--(-6.5,-1), edge); draw((4.5,-1)--(5,0)--(5.5,-1), edge); draw((6.5,-1)--(7,0)--(7.5,-1), edge); draw((7,-2)--(7.5,-1)--(8,-2), edge); leaf((4,1), 3, red, (-7,0)); leaf((3,4), 2, grey, (-5,0)); leaf((5,3), 4, grey, (-3,0)); leaf((2,5), 6, grey, (-1,0)); leaf((5,2), 3, grey, ( 1,0)); leaf((3,5), 6, grey, ( 3,0)); leaf((4,3), 1, grey, ( 5,0)); leaf((1,4), 2, heavycyan, ( 7,0)); leaf((3, 1), 2, grey, (-6,1.5)); leaf((2, 3), 4, blue, (-2,1.5)); leaf((3, 2), 3, red, ( 2,1.5)); leaf((1, 3), 1, grey, ( 6,1.5)); leaf((2, 1), 2, heavycyan, (-4,3)); leaf((1, 2), 1, grey, (4,3)); leaf((1, 1), 1, heavygreen, (0,4.5)); leaf((5, 1), 4, blue, (-7.5,-1)); leaf((4, 5), 3, grey, (-6.5,-1)); leaf((7, 3), 4, blue, ( 4.5,-1)); leaf((4, 5), 1, grey, ( 5.5,-1)); leaf((7, 3), 2, grey, ( 6.5,-1)); leaf((1, 5), 3, red, ( 7.5,-1)); leaf((6, 5), 3, grey, ( 7.0,-2)); leaf((1, 6), 4, blue, ( 8.0,-2)); [/asy][/asy] One quickly notices that every vertex $w$ has exactly one child with the same label $f(w)$. More is true: Lemma: Suppose $f(a,b) = k$. Then either $f(a+b,b) = k+b$ and $f(a,b+a) = k$, or $f(a+b,b) = k$ and $f(a,b+a) = k+a$. Proof. A computation gives that \[ f(a+b,b) = \begin{cases} k+b & \{a\nu\} + \{b\nu\} < 1 \\ k & \{a\nu\} + \{b\nu\} > 1, \end{cases} \quad f(a,a+b) = \begin{cases} k & \{a\nu\} + \{b\nu\} < 1 \\ k+a & \{a\nu\} + \{b\nu\} > 1 \end{cases} \]hence done. $\blacksquare$ We need one more property about the tree before we can forget about $\nu$ completely and do combinatorics: Lemma: For any fixed $b$, $\lim_{a \to \infty} f(a,b) = \infty$. Similarly, for any fixed $a$, $\lim_{b \to \infty} f(a,b) = \infty$. Colloquially, given a vertex $v$ in the tree, this means that if we always go right (or always go left) then the labels will not remain constant. (One possible way to notice this claim is to look for $2$ in the tree.) The stage is set, and we are actually almost done now. Alert readers may already notice this provides some guarantees about the structure of the tree: for example, if vertex $w = (a,b)$ is labeled with $L$, then if we follow the right path indefinitely, we will eventually run into $L+a$, $L+2a$, $L+3a$, et cetera. An even closer inspection (with two cases) shows that we'll actually run into $L+a+b$ too --- as well as $L+a+b$, $L+a+2b$, $L+2a+b$, and indeed any linear combination, and even with the right multiplicity. In other words if $w = (a,b)$ is labeled with $L$, we will show that the multiset of excellent descendants is exactly $\{ L + ia + jb \mid i,j \ge 0 \}$ (except for possibly $w$ itself). We write this formally as the following claim: Claim: Fix $m$. For any vertex $w = (a,b)$, the number of $m$-excellent children of $w$ is the number of pairs $i,j \ge 0$ with $(i,j) \neq (0,0)$ and $f(w) + ai + bj = m$. In particular applying the claim to $w = (1,1)$ solves the problem. The induction requires some care, however. Proof. [Proof of claim] We see (more or less by definition) that if the children of $w$ have the desired property, then so does $w$: this is the ``inductive step''. But the issue is the tree is infinite downwards, so we will need a trick to establish the base case. For a positive integer $m$, we say a vertex $w=(a,b)$ is $m$-dead if either $f(w) \ge m$ or $\min\{a,b\} \ge m$. Otherwise we say the vertex $w$ is $m$-alive. The naming comes from the idea that an $m$-dead vertex cannot have $m$-excellent children, or even $m$-alive children. Observe that by the second lemma above, there are only finitely many $m$-alive vertices in the whole tree. For there are only finitely many $m$-alive vertices with any given left or right coordinate. And now we are really done by induction, because we can take all cofinitely many $m$-dead vertices as base cases. $\blacksquare$

Let $g(a,b)=a\lceil bv \rceil-b\lfloor av \rfloor $ Some computations give that $$g(a+b,b)=g(a,b)+b... \text{if} ... \{av \}+\{ bv \} <1 ... g(a,b).. \text{if} ... \{av \}+\{ bv \}>1$$$$g(a,b+a)=g(a,b)... \text{if} ... \{av \}+\{ bv \} <1 ... g(a,b)+a.. \text{if} ... \{av \}+\{ bv \}>1$$. From approximation arguments we get that $ \{xv \}+\{ yv \} <1$ cannot hold for every $(a+kb,b)$ with $k$ going to infinity so that $g(a,b)$ tends to infinity as $a$ tends to infinity and the same holds for $b$. Now we are looking for $g(a,b)=m$ and $g(a-b,b)=m-b$ if $a>b$ and $g(a,b-a)=m-a$ if $b>a$.Now we say that a pair $(x,y)$ is a root of an excellent pair if $$ g(x,y)=m - tmax(x,y)$$for some positive number $t$. Since $$x>y \vdots g(x,y) \to g(x,x+y) \to g(x,2x+y) \to .... \to \text{excellent pair}$$$$x<y \vdots g(x,y) \to g(x+y,y) \to g(x+2y,y) \to .... \to \text{excellent pair}$$Since every excellent pair has a root (except $(m,m)$) and every root leads to an excellent pair we are going to work on the roots.Note that for a root $(x,y)$ you cannot have $max(x,y)>m-1$ and now we pass to the key concept of the solution.Every root $(x,y)$ belongs to $\{ 0,1,...,m-1\}^2$ For $v<1/m$ the counting of the roots gives the desired result. Now we will show that when $m$ passes from $k/l-e$ to$k/l+e$ for some irreducible fraction with $l<m$ the number of roots remains unchanged. the number of roots remains unchanged.We will simultaneously use induction on $m$ 1)Now consider those $(x,y)$ that neither of $x$ and $y$ is divided by $l$.Then $g(a,b)$ remains unchanged so the number of such roots remains unchanged. 2)Consider those roots $(x,y)$ that both $x,y$ are divided by $l$ .They result into an excellent pair $(a,b)$ such that $l | a$ and $l |b$ then $l$ divides $m$ as well and by replacing $m$ with $m/l$ and $v$ with $lv$ we show by induction on $m$ that the number of such pairs is stable. 3)Now consider those $(x,y)$ that exactly one of $x$ $y$ is divided by $l$. There are four cases for such roots we must work on$\to$$(al,b): al>b , (al,b): al<b , (b,al):al>b ,(b,al):al<b$ Compute $g(al,b)$ and $g(b,al)$ for $v=k/l-e$ and then for $v=k/l+e$ $$v=k/l-e \to$$$$ g(al,b)=a(l-bk(mod l))+b$$$$g(b,al)=a(bk(mod l))$$$$v=k/l+e \to$$$$g(al,b)=a(l-bk(modl))$$$$g(b,al)=a(bk(mod l))+b$$Now we will count roots in all possible cases.$\#$ stands for number. $1)v=k/l-e$ We need $$ al>b \to \#[a(l-bk(mod l))+b=m-tal] , \#[a(bk(mod l))=m-tal]$$$$ al<b \to \#[a(l-bk(mod l))+b=m-tb] , \#[a(bk(mod l))=m-tb]$$For positive $t$ $2)v=k/l+e$ We need $$ al>b \to \#[a(l-bk(modl))=m-tal] , \#[a(bk(mod l))+b=m-tal]$$$$ al<b \to \#[a(l-bk(modl))=m-tb] , \#[a(bk(mod l))+b=m-tb]$$For positive $t$ Now we will show that all roots in $1)$ and $2)$ have the same number. $\to$$ \#[a(bk(mod l))+b=m-tb]$ from $2)$ is contained in $\#[a(bk(mod l))=m-tb]$ from $1)$ and it leaves $\#[a(bk(mod l))=m-b]$ $\to$ $\#[a(l-bk(mod l))+b=m-tb]$ from $1)$ is contained in $\#[a(l-bk(modl))=m-tb]$ from $2)$ but it leaves $\#[a(l-bk(modl))=m-b]$ $\to$ $ \#[a(bk(mod l))=m-tal]$ from $1)$ and $\#[a(l-bk(modl))=m-tal]$ from $2)$ are equall cause for $c=al-b$ in $2)$ we get $ \#[a(ck(mod l))=m-tal]$ So now it remains to equallize $$ \#[a(l-bk(mod l))+b=m-tal] + \#[a(bk(mod l))=m-b]$$and, $$ \#[a(bk(mod l))+b=m-tal] + \#[a(l-bk(modl))=m-b]$$ So in $ \#[a(l-bk(modl))=m-b]$ we take $c=b(mod al)$ ,(we already have $b>al$), so that $c+tal=b$ . Here we clearly have $\#[a(l-ck(mod l))+c=m-tal]$, so finally $ \#[a(l-bk(modl))=m-b] =\#[a(l-bk(mod l))+b=m-tal]$. The same story for $ \#[a(bk(mod l))=m-b]= \#[a(bk(mod l))+b=m-tal]$. So we have shown that when $v$ passes a rational number then the number of roots and hence of excellent pairs remains unchanged. This in conjunction with computing the excellent pairs for $v \to 0$ finishes the problem. Phew this turned out to be quite lengthy.

Let $f(a, b) = a \lceil b \nu \rceil - b \lfloor a \nu \rfloor$. Say that $(a, b)$ is $m$-good if $f(a, b) = m$ and $m$-excellent if neither $(a - b, b)$ nor $(a, b - a)$ is $m$-good. Simple calculations show that \begin{align*} f(a + b, b) & = f(a, b) + \begin{cases*} b & if $\{a \nu\} + \{b \nu\} < 1$\\ 0 & if $\{a \nu\} + \{b \nu\} > 1$\\\end{cases*},\\ f(a, a + b) & = f(a, b) + \begin{cases*} 0 & if $\{a \nu\} + \{b \nu\} < 1$\\ a & if $\{a \nu\} + \{b \nu\} > 1$\\\end{cases*}. \end{align*} It is sufficient to show that there are exactly $m$ $m$-excellent pairs $(a, b)$ with $\gcd(a, b) = 1$. (Once this is proven, apply this for the numbers of the form $d \nu$, where $d \mid n$ to get the desired conclusion.) Store these pairs in a binary tree with root $(1, 1)$, where the children of $(a, b)$ are $(a, a + b)$ and $(a + b, a)$. We will only need to remember the following data about $f$: $f(1, 1) = 1$. For each $(a, b)$ in the tree, $\big(f(a, a + b), f(a + b, a)\big)$ equals one of $\big(f(a, b) + a, f(a, b)\big)$ or $\big(f(a, b), f(a, b) + b\big)$. The above property implies that from any node $k$, there is a unique infinite path descending from $k$ on which $f$ is constant. Then, this path must use infinitely many left children and infinitely many right children. This property follows from the fact that $\nu, 2 \nu, \dots$ is dense modulo 1. A more natural way to view this is that on any infinite path using only left children or only right children, $f$ must increment infinitely often. In other words, for any $u$ and $v$, \[\lim_{b \to \infty} f(u, b) = \infty \quad \text{and} \quad \lim_{a \to \infty} f(a, v) = \infty.\] Define $c_{n, a, b}$ to be the number of excellent descendants of $(a, b)$ with value $n$. (Here we consider $(a, b)$ to be an excellent descendant of itself.) Lemma 1. Let $n$ be a positive integer and let $(a, b)$ be a node in the tree. Then \[c_{n, a, b} = c_{n, a, a + b} + c_{n, a + b, b}.\] Proof. Follows from the fact that the subtree with root $(a, b)$ splits into two trees with roots $(a, a + b)$ and $(a + b, b)$. $\blacksquare$ Define $d_{n, a, b}$ to be the number of nonnegative integer solutions $(k, \ell)$ to $ka + \ell b = n - f(a, b)$. Lemma 2. Let $n$ be a positive integer and let $(a, b)$ be a node in the tree. Then \[d_{n, a, b} = d_{n, a, a + b} + d_{n, a + b, b}.\] Proof. Suppose that $f(a, a + b) = f(a, b) + a$ and $f(a + b, a) = f(a, b)$; the other case is similar. Note that \begin{align*} d_{n, a, a + b} + d_{n, a + b, b} & = [x^n] \frac{x^{f(a, a + b)}}{(1 - x^a)(1 - x^{a + b})} + \frac{x^{f(a + b, b)}}{(1 - x^{a + b})(1 - x^b)}\\ & = [x^n] \frac{x^{f(a, b) + a}}{(1 - x^a)(1 - x^{a + b})} + \frac{x^{f(a, b)}}{(1 - x^{a + b})(1 - x^b)}\\ & = [x^n] \frac{x^{f(a, b)}}{1 - x^{a + b}} \left(\frac{x^a}{1 - x^a} + \frac{1}{1 - x^b}\right)\\ & = [x^n] \frac{x^{f(a, b)}}{(1 - x^a)(1 - x^b)}\\ & = d_{n, a, b} \end{align*}as desired. $\blacksquare$ Now we prove the main claim. Main Claim. Let $n$ be a positive integer and let $(a, b)$ be a node in the tree. Then $c_{n, a, b} = d_{n, a, b}$. Proof. Go by induction on $d = d_{n, a, b}$. By the infinity limit properties of $f$ described above and the Lemmas, we only need to show this claim for $d \le 1$. The claim is clear for $d = 0$, since any path descending from $(a, b)$ can have values incremented only by numbers of the form $ua + vb$. Suppose $d = 1$. By the limit properties of $f$, there exists a descendant $(u, v)$ of $(a, b)$ with $d_{n, u, v} = 1$ and $u, v \ge n$. This forces $f(u, v) = n$; traveling upwards from $(u, v)$ to $(a, b)$, we see that $c_{n, a, b} = 1$. $\blacksquare$ Finally, by the main Claim, $c_{n, 1, 1} = d_{n, 1, 1} = n$, as desired.

Solved with eisirrational. Let $f(a,b)=a\lceil b\nu\rceil-b\lfloor a\nu\rfloor=a-a\{b\nu\}+b\{a\nu\}$. It suffices to prove, for any $\nu$, the number of excellent $(a,b)$ with $\gcd(a,b)=1$ is equal to $m$. To see this, let $f_\nu(a,b)$ denote $f(a,b)$ with that particular value of $\nu$; then the number of $(a,b)$ with $\gcd(a,b)=k$ and $f_\nu(a,b)=m$ equals the number of $(a',b')$ with $\gcd(a',b')=1$ and $f_{\nu k}(a',b')=m/k$. Then summing over all $k$ gives the desired result. Consider the binary tree whose nodes correspond to $(a,b)$ with $\gcd(a,b)=1$. Its root is $(1,1)$, and the left child of $(a,b)$ is $(a,a+b)$ and the right child $(a+b,b)$. By the Euclidean algorithm all $(a,b)$ with $\gcd(a,b)=1$ appear in the tree. Shown below is $\nu=\pi/2$.

The following two claims will eliminate $\nu$ from the problem. Claim: Let $f(a,b)=N$. Then if $\{a\nu\}+\{b\nu\}\ge1$, then $f(a,a+b)=f(a,b)+a$ and $f(a+b,b)=f(a,b)$. if $\{a\nu\}+\{b\nu\}<1$, then $f(a,a+b)=f(a,b)$ and $f(a+b,b)=f(a,b)+b$. Proof. Note $\{a\nu\}+\{b\nu\}-\{(a+b)\nu\}$ equals $0$ if $\{a\nu\}+\{b\nu\}\le1$ and $1$ otherwise. It is easy to compute $f(a,a+b)=a-a\{(a+b)\nu\}+a\{a\nu\}+b\{a\nu\}$. $f(a+b,b)=a+b-a\{b\nu\}-b\{b\nu\}+b\{(a+b)\nu\}$; Hence, we have $f(a,a+b)-f(a,b)=a(\{a\nu\}+\{b\nu\}-\{(a+b)\nu\})$; $f(a+b,b)-f(a,b)=b(1-\{a\nu\}-\{b\nu\}+\{(a+b)\nu\})$. This verifies the claim. $\blacksquare$ Claim: If $f(a,b)=N$, then there is a postive integer $n$ with $f(a,b+an)=N+a$. (Similarly, there is an $m$ with $f(a+bm,b)=N+b$.) Proof. Assume not. Then $f(a,b+an)=N$ for all $n$. In particular, $\{a\nu\}+\{(b+an)\nu\}<1$ for all $n$, but $\nu$ is irrational, so $\nu$, $2\nu$, $\ldots$ is dense in $(0,1)$, contradiction. $\blacksquare$ Claim: [Main claim] Let $f(a,b)=N$. Then the number of descendants of $(a',b')$ with $f(a',b')=N+T$ is the number of nonnegative $m$ and $n$ with $T=ma+nb$. Proof. First we check that if the claim holds for $(a,a+b)$ and $(a+b,b)$, then it holds for $(a,b)$. Without loss of generality $f(a,a+b)=N+a$ and $f(a+b,a)=N$. Consider each representation of $T$ as a linear combination $ma+nb$. Then $T=a+(m-n-1)a+n(a+b)$ is in the subtree of $(a,a+b)$ if and only if $m>n$; $T=m(a+b)+(n-m)b$ is in the subtree of $(a+b,b)$ if and only if $m\le n$. Thus it suffices to find cofinitely many base cases. Consider any path starting from $(a,b)$ going down. At some point, there is a point $(a',b')$ such that either $f(a',b')>T$, or both $f(a',b')+a'>T$ and $f(a',b')+b'>T$ since $f(a',b')$ cannot remain constant while one of $a'$, $b'$ is bounded by the second claim. $\blacksquare$ Taking $(a,b)=(1,1)$ in the above claim provides the desired conclusion.

Note it suffices to show the following claim. Claim: [Sufficient Result] Let $\nu$ be an irrational real number. Define $f(a,b) = a\lceil b\nu\rceil - b\lfloor a\nu\rfloor$. Say that a pair $(a,b)$ of positive integers is excellent if $\gcd(a,b)=1$ and each of $(x,y)=(a-b,b),(a,b-a)$ either satisfies $f(x,y)\ne f(a,b)$ or one of $x,y$ is nonpositive. Prove that for any positive integer $m$, the number of excellent pairs with $f(a,b)=m$ is exactly $m$. This claim suffices by considering each possible value of $\gcd(a,b)=d\mid m$ and applying the result on $\nu'=d\nu$. Now, consider draw a tree on pairs of relatively prime positive integers as follows; there is an edge between any pair $(a,b),(a+b,b)$ and any pair $(a,b),(a,a+b)$. By the Euclidean Algorithm, this is, in fact, a tree. Then, an excellent pair $(a,b)$ is a pair such that its parent $(x,y)$ has $f(a,b)\ne f(x,y)$. Now, observe the following relation; we have \[f(a+b,b) = (a+b)\lceil b\nu\rceil - b\lfloor (a+b)\nu\rfloor = a\lceil b\nu\rceil - b\lfloor a\nu\rfloor + \left[b\lceil b\nu\rceil - b\left(\lfloor (a+b)\nu\rfloor - \lfloor a\nu\rfloor\right)\right]=\]\[f(a,b)+ b\left[\lceil b\nu\rceil - \left(\lfloor (a+b)\nu\rfloor \frac{\phantom{.}}{\phantom{\emptyset}} \lfloor a\nu\rfloor\right)\right].\]The latter expression is $b$ when $\lfloor (a+b)\nu\rfloor - \lfloor a\nu\rfloor = \lfloor b\nu\rfloor$ and $0$ otherwise. Similarly, we have \[f(a,a+b) = f(a,b) + a\left[\left(\lceil (a+b)\nu\rceil \frac{\phantom{.}}{\phantom{\emptyset}} \lceil b\nu\rceil\right) - \lfloor a\nu\rfloor\right],\]where the expression added to $f(a,b)$ is $a$ when $\lceil (a+b)\nu\rceil - \lceil b\nu\rceil = \lceil a\nu\rceil$ and $0$ otherwise. Moreover, we have $f(1,1)=1$. Now, we claim that exactly one of $\lfloor (a+b)\nu\rfloor - \lfloor a\nu\rfloor = \lfloor b\nu\rfloor$ and $\lceil (a+b)\nu\rceil - \lceil b\nu\rceil = \lceil a\nu\rceil$ is true for any relatively prime pair of positive integers $(a,b)$. This is an exercise in arithmetic; clearly, \[\lfloor a\nu\rfloor + \lfloor b\nu\rfloor +1\ge \lfloor (a+b)\nu\rfloor\]and similarly \[\lceil (a+b)\nu\rceil \ge \lceil a\nu\rceil+\lceil b\nu\rceil - 1.\]As $\nu$ is irrational, we have $\lfloor k\nu\rfloor = \lceil k\nu\rceil -1$ for any integer $k$, so by checking cases we see that exactly one of $\lfloor (a+b)\nu\rfloor - \lfloor a\nu\rfloor = \lfloor b\nu\rfloor$, $\lceil (a+b)\nu\rceil - \lceil b\nu\rceil = \lceil a\nu\rceil$ holds for any choice of $(a,b)$. Now, consider a chain \[(a,b)\to (a,b+a)\to\cdots\to (a,b+ka)\to (a,b+(k+1)a) \to\cdots.\]We claim that for each nonnegative integer $\ell$, $f(a,b)+a\ell$ is $f(a,b+ka)$ for some nonnegative integer $k$. We induct on $\ell$. The base case is trivial. Note that the induction step for showing $f(a,b)+a\ell$ is achievable for any particular $\ell>0$ is isomorphic to showing that $f(a,b)+\ell$ is attainable, so we show the latter. Now, note that for any $k$, we have \[f(a,b+ka) = f(a,b)+\sum_{i=1}^k (f(a,b+ia) - f(a,b+(i-1)a)) = f(a,b)+\sum_{i=1}^k a\left[\left(\lceil (b+ia)\nu\rceil \frac{\phantom{.}}{\phantom{\emptyset}} \lceil (b+(i-1)a)\nu\rceil\right) - \lfloor a\nu\rfloor\right]=\]\[f(a,b)+a\sum_{i=1}^k \left[\left(\lceil (b+ia)\nu\rceil \frac{\phantom{.}}{\phantom{\emptyset}} \lceil (b+(i-1)a)\nu\rceil\right) - \lfloor a\nu\rfloor\right]=f(a,b)+a \left[\left(\lceil (b+ka)\nu\rceil \frac{\phantom{.}}{\phantom{\emptyset}} \lceil b\nu\rceil\right) - k\lfloor a\nu\rfloor\right].\]Note that if any of the partial sums $a\left[\left(\lceil (b+ia)\nu\rceil \frac{\phantom{.}}{\phantom{\emptyset}} \lceil (b+(i-1)a)\nu\rceil\right) - \lfloor a\nu\rfloor\right]$ was nonzero, that is, equal to $a$, we would be done; take the smallest such index $i$ and consider $f(a,b+ia)$. Otherwise, assume for contradiction that for all positive integers $k$, we have \[\left(\lceil (b+ka)\nu\rceil - \lceil b\nu\rceil\right) - k\lfloor a\nu\rfloor=0.\]That is, suppose that for all $k\in \mathbb{Z}_{>0},$ we have \[k\lfloor a\nu\rfloor + \lceil b\nu\rceil= \lceil (b+ka)\nu\rceil.\]Now, note there must exist some positive integer $n$ for which $\{a\nu\}$ (the fractional part of $a\nu$) is greater than $\frac{1}{n}$, as otherwise we would have $a\nu$ is an integer, as we would get $\frac{1}{n}\ge\{a\nu\}$ for all positive integers $n$, and $\inf \frac{1}{n} = 0$. Write $m=a\nu-\{a\nu\}$ to see $m+1>\nu>m+\frac{1}{n}$. Take $k=n$ to see that \[mn + \lceil b\nu\rceil = \lceil (b+ka)\nu\rceil \ge \lceil b\nu\rceil + \lfloor na\nu\rfloor \ge \lceil b\nu\rceil + \lfloor nm+1\rfloor = \lceil b\nu\rceil + nm+1,\]absurd. Hence, we have a contradiction and some such $k$ exists for each $\ell$. Similarly, for each nonnegative integer $\ell$, there exists a nonnegative integer $k$ such that $f(a,b)+b\ell = f(a+kb,a)$. Now, we use the following argument to extract the answer. Let $P$ denote the statement that ``the number of descendants of $(a,b)$ in the tree (including itself), $(k,\ell)$, with $f(k,\ell)=m$ is equal to the number of pairs $(x,y)$ of nonnegative integers with $xa+yb+f(a,b)=m$.'' This statement is trivial when $f(a,b)\ge m$, now we induct upwards in the tree. Consider a vertex $(a,b)$ of the tree with children $(a+b,b),(a,a+b)$. Suppose $f(a,b)<m$, as we are done otherwise. WLOG, suppose $f(a,a+b)=f(a,b)$. Let $m-f(a,b)=u$. By the induction hypothesis, $(a,b)$ must have descendants $k,\ell$ with $f(k,\ell)=m$ equal to the number of pairs $(x,y)$ of nonnegative integers with $xa+y(a+b)=u$ added to the number of pairs $(w,z)$ of nonnegative integers with $w(a+b)+zb=u-b$. The first equation rearranges to $(x+y)a+yb=u$ and the latter rearranges to $wa+(w+z+1)b=u$. But the total number of pairs $(x,y)$ and $(w,z)$ must be the number of nonnegative integer pairs $(c,d)$ with $ca+db=u$; the pairs $(x,y)$ correspond to when $c\ge d$ and the pairs $(w,z)$ correspond to when $c<d$. Hence, the inductive hypothesis holds. Finally, it is clear that there are $m$ pairs of nonnegative integers $x,y$ with $x\cdot1+y\cdot1=m-1=m-f(1,1)$, so we are done.

I found something wrong.Deleted.

There's an elegant solution... but I don't wanna find it. Let $(a, b)$ denote $a \lceil b \nu \rceil - b \lfloor a \nu \rfloor$. Let $(a, b)$ on nonpositive pairs be $0$. Notice trivially that $(a, b) = k$ implies $(a - b, b), (a, b - a) \leq k$. Furthermore notice that by inequality casework on whether $\{a\nu\} + \{b\nu\} \geq 1$, for each $(a, b) = k$, either $(a+b, b) = k, (a, a+b) = k+a$ or $(a+b, b) = k+b, (a, a+b) = k$. Now, consider the set of pairs $(a, b)$ such that $gcd(a, b) = 1$. I claim the number of solutions to $(a, b) = m$ that are generated from $(1, 1)$ is precisely $m$. To prove this, first notice the generation process from $(1, 1)$ forms an infinite binary tree, whose branches must be unbounded since $\nu$ is irrational. Then I claim the number of solutions to $(a, b) = m$ that can be generated from $(c, d) = m'$ is precisely the number of solutions in $x, y \in \mathbb{N}_0$ to $cx + dy + m' = m$. We do this by backward induction, where the base cases are trivial, and each previous case can be concluded simply from casework on either $x \leq y$ vs $x > y$ or $x \geq y$ vs $x < y$ depending on which generation case is used. Either way, this is a finite induction so since the number of solutions to $x + y = m - 1$ is precisely $m$, we have proven this paragraph's claim. Now notice that we may simply to casework on the possible values of $\gcd(a, b)$. Specifically by scaling both $a, b$, and $(a, b)$ in these cases, we have that if $\gcd(a, b) = d \mid m$ then the number of solutions is precisely $\frac{m}{d}$, so it follows that summing over all values of $d$ gives a total of $\sigma(m)$ solutions as desired.

Fix $\nu$ and $m$. Let $f(a,b)=a\lceil b\nu\rceil-b\lfloor a\nu\rfloor$. We start with two technical lemmas, whose proofs we omit as they are not hard to check using routine floor function arithmetic/casework. Lemma: We have either $f(a+b,b)=f(a, b)+b$ and $f(a,a+b)=f(a, b)$, or $f(a+b,b)=f(a, b)$ and $f(a,a+b)=f(a, b)+a$. Lemma: Fix $b$. Then as $a \rightarrow \infty$, $f(a, b) \rightarrow \infty$. The key idea is that, upon multiplying $\nu$ by some integer $d > 0$, $f(a, b)$ multiplies by $d$. Thus, proving that the number of excellent pairs $(a, b)$ where $\gcd(a, b)=1$ equals $m$ is sufficient. For the sake of visualization, draw the binary tree for coprime pairs by following the Euclidean algorithm, and label each pair $(a, b)$ with $f(a, b)$. Now consider the process in which one starts at $(a, b)$ and moves down the binary tree (with possibly 2 choices for a move) until it is impossible to go down so that at least one component is at most $m$, and $f(a, b)$ is at most $m$. Let $\chi(a, b)$ denote the number of excellent pairs generated in the process (excluding $(a, b)$). By casework on the next vertex in the path, \[ \chi(a, b) = \chi(a, a + b) + \chi(a + b, b).\]We say that the R2D2 series for a given vertex $(a, b)$ of the binary tree is the generating function \[ F_{(a, b)}(x) := x^{f(a, b)}(1-x^a)^{-1}(1-x^b)^{-1}. \]The significance of this is that the number of nonnegative integer solutions $(i, j)$ to $ai + bj + f(a, b) = m$ (which we denote by $\alpha(a, b)$) is the coefficient of $x^m$ in the R2D2 series for $(a, b)$. Funnily enough, \[ F_{(a, a+b)} + F_{(a+b, b)} = F_{(a, b)}, \]so $\chi(a, b)=\alpha(a, b)$ by induction, since we only need to check the cases where $\alpha(a, b) \le 1$ for the base case, and the inductive step is already done. Thus $\chi(1, 1)=\alpha(1, 1)=m$, as desired. $\blacksquare$