# Bamboo Garden Trimming Problem: Priority Schedulings +
## 3 Theoretical Results
### Priority Schedulings  
Let \(\mathcal{C}\) be the set of any configuration of \(n\) bamboos. **Definition 1**: _An oblivious scheduling \(\sigma:\mathcal{C}\to\{0,1,\ldots,n\}\) is a function which for any configuration of heights in \(\mathcal{C}\) returns an index \(i\) of the bamboo to be cut, and \(i=0\) means that none of the bamboos is scheduled to be cut._  
In other words, in oblivious schedulings the next cut is solely based on the current configuration, without exploiting any knowledge about past cuts. **Definition 2**: _A configuration \(C=(\ell_{1},\ell_{2},\ldots,\ell_{n})\) is said to be ordered whenever \(i<j\) implies \(h_{i}\geq h_{j}\)._  
The above implies the order of the sequence in \(C\) reflects a non-increasing ordering of the growth rates, i.e., \(\ell_{1}\) is the height of the bamboo with the biggest growth rate. **Definition 3**: _An ordered oblivious scheduling \(\sigma:\mathcal{O}\to\{0,1,\ldots,n\}\) is an oblivious scheduling where \(\mathcal{O}\subset\mathcal{C}\) is the set of ordered configurations in \(\mathcal{C}\)._  
**Definition 4**: _Given a threshold \(\tau\geq H\) and any (ordered) configuration \(C\in\mathcal{C}\), let \(L\) be the set of indices of all bamboos whose height is strictly greater than \(\tau\). An oblivious scheduling \(\sigma_{\tau}\) is a (ordered) \(\tau\)-priority scheduling if and only if \(L\
eq\emptyset\) implies \(\sigma_{\tau}(C)\in L\)._  
In the remainder of the paper, a (ordered) \(\tau\)_-priority scheduling_ is simply referred to as a _priority scheduling_ when the ordering and the value of \(\tau\) are either clear from the context or irrelevant. Clearly, ReduceFastest  
The next lemma gives an upper bound on the volume the garden may reach in a priority scheduling. This is useful to prove that any priority scheduling stabilises into a cycle of finite length. **Lemma 1** (Upper Bound on Volume). : _Given a \(\tau\)-priority scheduling \(\sigma_{\tau}\) and an input \(I\), there exists a time \(t\), such that, for any \(t^{\prime}>t\), it holds \(V(C^{t^{\prime}})\leq n\tau\), where \(C^{t^{\prime}}\in E(I,\sigma_{\tau})\)._  
Proof. : First, assume that \(M(E(I,\sigma_{\tau}))>\tau\), as otherwise \(V(C)\leq n\tau\), for each \(C\in E(I,\sigma_{\tau})\), and the lemma holds. If it is also assumed \(M(C^{0})>\tau\) then it is possible to prove that, within finite time, a configuration \(C\) with \(M(C)\leq\tau\) is reached by applying \(\sigma_{\tau}\). In particular, note that for as long as there are bamboos having height greater than \(\tau\), the total volume decreases each day, being \(\tau\geq H\), of at least 1. Thus, there must exist a time \(t\) when eventually \(M(C^{t})\leq\tau\), since the volume cannot decrease indefinitely. At this time, it holds \(V(C^{t})\leq n\tau\). Therefore, let \(t^{\prime}>t\) be the first day after time \(t\) such that \(C^{t^{\prime}}\) has a bamboo having height greater than \(\tau\). Clearly, \(V(C^{t^{\prime}})<V(C^{t^{\prime}-1})-\tau+H\), as \(\sigma_{\tau}\) cuts a bamboo with height greater than \(\tau\) and, at the end of the day, all bamboos grow by \(H\) in total. Moreover, by hypothesis \(V(C^{t^{\prime}-1})\leq n\tau\), since \(\ell_{i}\leq\tau\), for each \(\ell_{i}\in C^{t^{\prime}-1}\). Hence,  
\[V(C^{t^{\prime}})<(n-1)\tau+H\leq n\tau\]  
as \(H\leq\tau\). Now, by focussing on \(V(C^{t^{\prime}+1})\), since in \(C^{t^{\prime}}\) the scheduling algorithm cuts a bamboo having height bigger than \(\tau\), and since the sum of daily growths is exactly \(H\), it follows that \(V(C^{t^{\prime}+1})<V(C^{t^{\prime}})\). This is actually true for any following configuration until day \(t^{\prime\prime}\) where \(\ell_{i}\leq\tau\) for any \(\ell_{i}\in C^{t^{\prime}}\). Notice that in \(t^{\prime\prime}\), the same set of hypotheses as of day \(t\) hold, then by repeating the reasoning, the claim follows. By Lemma 1, the next corollary can be obtained, which guarantees that any priority scheduling stabilises into a cycle of finite length, i.e., that the sequence of cuts becomes periodic.