Scheduling Dashain Tika

Exact bounds on sitting and standing costs

PDF · Quarto source · Executed notebook · Source bundle · Figure files

1 The scheduling problem

During Dashain, elders give tika and blessings to younger family members. Consider a gathering with the following rule: every person gives tika to everyone younger than them, one pair at a time. A recipient sits to receive tika and eventually stands to leave. Repeating this for each elder can mean many sit–stand cycles. The scheduling question is whether changing the order can reduce that movement while completing every required tika.

Assume distinct ages and index the N\geq2 people from youngest, 1, to eldest, N. Each older person gives exactly once to each younger person, so the required directed dyads are

\mathcal E=\{(i,j):1\leq j<i\leq N\},\qquad M=|\mathcal E|=\binom N2.

In (i,j), person i gives and person j receives. A schedule is a permutation \pi=((g_t,r_t))_{t=1}^M of \mathcal E. Interactions occur sequentially. Age determines the direction of each interaction. The schedule determines when it happens.

Let e be the combined cost of sitting down and subsequently standing up once. If each individual action costs e, replace this cycle cost by 2e.

1.1 Eldest-first policy

Person N gives tika to N-1,N-2,\ldots,1, in that order. Person N-1 then gives to N-2,\ldots,1, and so on until person 2 gives to person 1. Thus the dyads are processed as

(N,N-1),(N,N-2),\ldots,(N,1), (N-1,N-2),\ldots,(2,1).

In this baseline, the recipient sits and stands for every tika, even when their next interaction immediately follows. The number of recipient cycles is

(N-1)+(N-2)+\cdots+1=M, \qquad C_{\mathrm{recipient}}=Me.

If the giver also sits, each giver can remain seated throughout their block. Counting both roles then gives M+N-1 cycles and cost (M+N-1)e. These two accounting conventions lead to the respective comparisons below.

NoteOptimal sitting and standing costs

For a fixed giver position and recipient position, let c_G,c_R\geq0 be the respective costs of a seated episode. Each episode includes entry, consecutive interactions in that role, and exit. The exact minimum is

\boxed{\begin{aligned} C^*={}&(N-1)\max(c_G,c_R)\\ &+(M-N+2)\min(c_G,c_R). \end{aligned}}

Batch the more expensive role and retain the other occupant at each block boundary. The schedules below attain this bound.

The physical arrangement determines the relevant special case:

Arrangement	Minimum total sit–stand cost
One recipient sits; givers can approach with zero charged seating cost	(N-1)e
One giver seat and one recipient seat; both occupants’ cycles cost e	(M+1)e
Everyone can remain seated and all pairs can interact from their seats	Ne

The first two cases follow from the boxed formula. The fully seated case is a separate arrangement with enough seats and access between every pair. All costs include initial sitting and final standing. Every arrangement still requires M tikas.

1.2 Comparing the dyads

For four people, every schedule contains the same six older-to-younger pairs. Figure 1 shows their execution order and the resulting seated episodes. Recipient batching reduces the recipient count from six to three; both optimized orders attain the two-seat minimum of seven total cycles. The giver-block construction also preserves eldest-first priority among givers.

from pathlib import Path
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, Rectangle, FancyBboxPatch
import numpy as np

Path("figures").mkdir(exist_ok=True)

def export_figure(fig, name):
    fig.savefig(f"figures/{name}.svg", bbox_inches="tight")
    fig.savefig(f"figures/{name}.png", dpi=180, bbox_inches="tight")
    plt.show()

# Fixed four-person examples; checked against the constructors below.
dyad_examples = [
    ("Eldest first · recipient resets", True,
     [(4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)]),
    ("Optimal recipient batching", False,
     [(4, 3), (4, 2), (3, 2), (3, 1), (4, 1), (2, 1)]),
    ("Optimal two-seat giver blocks", False,
     [(4, 3), (4, 1), (4, 2), (3, 2), (3, 1), (2, 1)]),
]

fig, axes = plt.subplots(3, 1, figsize=(7.7, 7.1), constrained_layout=True)
for ax, (title, reset, order) in zip(axes, dyad_examples):
    counts = []
    for role, y, label, edge, fill in [
        (0, 1, "Giver", "#8e4b16", "#fff0df"),
        (1, 0, "Recipient", "#17627a", "#dceff5"),
    ]:
        bands = []
        for t, pair in enumerate(order):
            if t == 0 or pair[role] != order[t - 1][role] or (reset and role == 1):
                bands.append([t, t, pair[role]])
            else:
                bands[-1][1] = t
        counts.append(len(bands))
        for start, end, person in bands:
            ax.add_patch(FancyBboxPatch(
                (start - .34, y - .25), end - start + .68, .5,
                boxstyle="round,pad=0.015,rounding_size=0.12",
                facecolor=fill, edgecolor=edge, linewidth=1.4))
        for t, pair in enumerate(order):
            ax.text(t, y, str(pair[role]), ha="center", va="center",
                    fontsize=16, weight="bold", color=edge)
        ax.text(-.63, y, label, ha="right", va="center", fontsize=11, color=edge)
    for t in range(6):
        ax.text(t, 1.52, f"{t + 1}", ha="center", va="center", fontsize=10, color="#64748b")
        ax.annotate("", xy=(t, .29), xytext=(t, .71),
                    arrowprops={"arrowstyle": "->", "color": "#475569", "lw": 1.4})
    g, r = counts
    ax.text(-.63, 1.52, "Step", ha="right", va="center", fontsize=10, color="#64748b")
    ax.text(-1.5, -.71, f"Recipient only: {r}e", fontsize=12, weight="bold", color="#17627a")
    ax.text(1.35, -.71, f"Two seats: {g}e + {r}e = {g + r}e", fontsize=12, weight="bold")
    ax.set_title(title, loc="left", fontsize=13, weight="bold", pad=8)
    ax.set(xlim=(-1.55, 5.55), ylim=(-.86, 1.75))
    ax.axis("off")
export_figure(fig, "dyad-comparison")

Figure 1: The same six directed dyads in three schedules, read from left to right. Each downward arrow is one tika, from the numbered giver to the numbered recipient. Each continuous band is one seated episode, including its eventual stand-up. The baseline resets the recipient after every tika. Recipient batching is optimal for recipient-only costs; both lower schedules are optimal for equal-cost two-seat service. All costs use e per sit–stand cycle.

2 A setup-cost model

There is an active giver position and an active recipient position. Consecutive interactions can reuse an occupant in the same role. Changing roles starts a new role episode. Under the two-seat interpretation, the chairs have fixed roles; the participant gets up to change chairs.

Let c_G\geq0 be the cost of one giver episode and c_R\geq0 the cost of one recipient episode. A seated episode includes entry, any number of consecutive interactions in that role, and exit. Count episodes by

G(\pi)=1+\sum_{t=1}^{M-1}\mathbf1\{g_{t+1}\ne g_t\},\qquad R(\pi)=1+\sum_{t=1}^{M-1}\mathbf1\{r_{t+1}\ne r_t\}.

For any schedule, keep the occupant seated across consecutive uses of the same role. Additional stand–sit resets only increase its cost. The objective is

\min_\pi C(\pi),\qquad C(\pi)=c_GG(\pi)+c_RR(\pi).

This model describes two different practical cases. Setting (c_G,c_R)=(0,e) allows givers to approach a seated recipient, with their movement uncharged. Setting (c_G,c_R)=(e,e) charges both people at a two-seat station. Walking, waiting, tray transfers, and reaching costs are excluded. They can change which arrangement is attractive.

If each tika itself takes time \tau, total duration is \tau M+C(\pi) when the setup costs are measured in time. The number of tikas stays quadratic in N, even when movement costs become linear.

3 Three lower bounds and an exact optimum

Every person 2,\ldots,N must give, and every person 1,\ldots,N-1 must receive. Therefore

G(\pi)\geq N-1,\qquad R(\pi)\geq N-1.

Two consecutive interactions are distinct, so at least one of their giver and recipient identities changes. The first interaction starts two episodes; the remaining M-1 interactions each start at least one. Consequently,

G(\pi)+R(\pi)\geq M+1.

These three inequalities establish the lower bound in the introductory box.

Lower bound. Suppose c_R\geq c_G. Then

\begin{aligned} C(\pi) &=c_G\{G(\pi)+R(\pi)\}+(c_R-c_G)R(\pi)\\ &\geq c_G(M+1)+(c_R-c_G)(N-1)\\ &=c_R(N-1)+c_G(M-N+2). \end{aligned}

The case c_G\geq c_R follows by interchanging the roles. The constructions in the next section attain the bound. This proves global optimality over all M! schedules. No probabilistic approximation is required.

The rule is to batch the more expensive role, keeping its occupant in place for all their interactions, and arrange the block boundaries to retain the other occupant too.

4 Constructing optimal schedules

The following constructors generate the schedules illustrated below.

def eldest_first(n):
    return [(i, j) for i in range(n, 1, -1)
            for j in range(i - 1, 0, -1)]

def giver_blocks(n):
    order = []
    for i in range(n, 1, -1):
        recipients = [i - 1] + list(range(i - 3, 0, -1))
        if i >= 3:
            recipients += [i - 2]
        order.extend((i, j) for j in recipients)
    return order

def recipient_blocks(n):
    return [(n + 1 - j, n + 1 - i)
            for i, j in reversed(giver_blocks(n))]

def episodes(order):
    if not order:
        return 0, 0
    g = 1 + sum(a[0] != b[0] for a, b in zip(order, order[1:]))
    r = 1 + sum(a[1] != b[1] for a, b in zip(order, order[1:]))
    return g, r

def optimal_schedule(n, c_g, c_r):
    return giver_blocks(n) if c_g >= c_r else recipient_blocks(n)

4.1 Recipient batching: the linear-cost case

Seat person N-1 and have every older person give them tika. Then seat person N-2 and repeat, continuing to person 1. Every recipient sits once:

R=N-1,\qquad C=(N-1)e\quad\text{when }c_G=0,\ c_R=e.

Every recipient must sit at least once, so this already attains the lower bound. Compared with Me, the saving is

Me-(N-1)e=\frac{(N-1)(N-2)}2e, \qquad \frac{Me}{(N-1)e}=\frac N2.

For N=10, there are still 45 tikas, while recipient sit–stand cycles fall from 45 to 9. Givers must be able to approach the current recipient.

fig, axes = plt.subplots(2, 1, figsize=(8, 5.1), constrained_layout=True)
for ax, order, reset, title in [
    (axes[0], eldest_first(4), True, "Reset after each tika: 6 recipient episodes"),
    (axes[1], recipient_blocks(4), False, "Batch by recipient: 3 recipient episodes"),
]:
    bands = []
    for t, (_, r) in enumerate(order):
        if reset or t == 0 or order[t - 1][1] != r:
            bands.append([t, t + 1, r])
        else:
            bands[-1][1] = t + 1
    for start, end, r in bands:
        ax.add_patch(Rectangle((start + .08, r - .23), end - start - .16, .46,
                               facecolor="#d1e8f0", edgecolor="#17627a", linewidth=1.6))
        ax.text((start + end) / 2, r, str(r), ha="center", va="center", fontsize=12)
    for t in range(7):
        ax.axvline(t, color="#e2e8f0", lw=.7, zorder=0)
    ax.set(xlim=(0, 6), ylim=(.45, 3.55), yticks=[1, 2, 3],
           yticklabels=["Person 1", "Person 2", "Person 3"],
           xticks=np.arange(6) + .5,
           xticklabels=[f"{g} → {r}" for g, r in order],
           xlabel="Tikas in execution order: giver → recipient")
    ax.set_title(title, loc="left", fontsize=13, weight="bold", pad=9)
    ax.spines[["top", "right", "left"]].set_visible(False)
    ax.tick_params(axis="y", length=0)
export_figure(fig, "recipient-batching")

Figure 2: Recipient-only seating costs, illustrated with four people and six tikas. Each blue band is one sit–stand episode: it begins when a person sits and ends when they stand. The upper policy resets the recipient after every tika; the lower policy lets each recipient remain seated through all their elders. Giver movement is uncharged.

4.2 Giver blocks with a shared recipient at each boundary

When giver episodes are at least as expensive as recipient episodes, preserve the eldest-first giver blocks. In the block for giver i\geq3, use this recipient order:

i-1,\quad i-3,i-4,\ldots,1,\quad i-2.

The middle list is empty when i=3. Giver 2 visits recipient 1. Thus giver i finishes with recipient i-2, who stays seated while giver i-1 takes over and also starts with i-2.

For N=4, the schedule is

\underbrace{(4,3),(4,1),(4,2)}_{\text{giver 4}} \ ;\ \underbrace{(3,2),(3,1)}_{\text{giver 3}} \ ;\ (2,1).

Each boundary changes the giver alone. Within a block, only the recipient changes. There are N-1 giver episodes and M+1 total episodes:

G=N-1,\qquad R=M-N+2.

def seated_person(ax, x, y, person, color):
    ax.add_patch(Circle((x, y), .27, facecolor="white", edgecolor=color, linewidth=2.2))
    ax.text(x, y, str(person), ha="center", va="center", fontsize=16, weight="bold", color=color)
    ax.plot([x - .35, x + .35], [y - .42, y - .42], color=color, lw=2)
    ax.plot([x - .35, x - .35], [y - .25, y - .65], color=color, lw=2)
    ax.plot([x + .35, x + .35], [y - .42, y - .65], color=color, lw=2)

def handoff_figure(before, after):
    fig, ax = plt.subplots(figsize=(7.7, 3.7))
    ax.set(xlim=(-.8, 6.1), ylim=(-1.1, 2.1))
    ax.axis("off")
    labels = ["Giver", "Recipient"]
    for k, x in enumerate([.8, 3.0]):
        kept = before[k] == after[k]
        color = "#087f72" if kept else "#ad5713"
        ax.text(x, 1.92, labels[k], ha="center", fontsize=12, weight="bold")
        for y, pair in [(1.35, before), (0, after)]:
            seated_person(ax, x, y, pair[k], color)
        if kept:
            ax.text(x, -.91, "Stays seated", ha="center", color=color, fontsize=11, weight="bold")
    for y, label in [(1.35, "Before"), (0, "After")]:
        ax.text(-.65, y, label, ha="left", va="center", fontsize=11)
        ax.annotate("", xy=(2.58, y), xytext=(1.22, y),
                    arrowprops={"arrowstyle": "->", "color": "#64748b", "lw": 1.5})
    changed = 0 if before[0] != after[0] else 1
    kept = 1 - changed
    ax.text(4.05, 1.30, f"{labels[kept]} {before[kept]} stays", color="#087f72", fontsize=12, weight="bold")
    ax.text(4.05, .78, f"Person {before[changed]} stands.\nPerson {after[changed]} sits.", fontsize=11, linespacing=1.6)
    ax.text(4.05, -.12, "One new episode", fontsize=12, weight="bold")
    fig.tight_layout()
    return fig

order = giver_blocks(4)
fig = handoff_figure(order[2], order[3])
export_figure(fig, "giver-handoff")

Figure 3: A boundary between giver blocks in the four-person schedule: (4,2) is followed by (3,2). Recipient 2 stays seated while giver 4 is replaced by giver 3. The full six-tika schedule uses three giver episodes and four recipient episodes, attaining the two-seat minimum of seven.

4.3 Recipient blocks with a shared giver at each boundary

For c_R\geq c_G, use the symmetric construction. Recipient N-1 first receives from giver N. For each subsequent recipient j=N-2,\ldots,1, the giver order is

j+2,\quad N,N-1,\ldots,j+3,\quad j+1.

The middle list can be empty. Recipient j ends with giver j+1, who also starts the block for recipient j-1. The same giver stays in place across each boundary. The executable construction obtains this schedule by reversing the giver-block schedule, age labels, and role labels.

For N=4, this gives

(4,3)\ ;\ \underbrace{(4,2),(3,2)}_{\text{recipient 2}} \ ;\ \underbrace{(3,1),(4,1),(2,1)}_{\text{recipient 1}}.

The recipient blocks proceed in descending age order, so each person receives from all their elders before giving to anyone younger. The episode counts are

R=N-1,\qquad G=M-N+2.

order = recipient_blocks(4)
fig = handoff_figure(order[2], order[3])
export_figure(fig, "recipient-handoff")

Figure 4: A boundary between recipient blocks: (3,2) is followed by (3,1). Giver 3 stays seated while recipient 2 is replaced by recipient 1. The full four-person schedule uses four giver episodes and three recipient episodes. This construction is optimal when recipient episodes are at least as costly as giver episodes.

The two constructions satisfy the lower bound for their respective cost ordering. They each enumerate all M required interactions in O(M) time.

4.4 What the two-seat restriction permits

With c_G=c_R=e, either construction achieves

C^*=(M+1)e.

This is also optimal when the two chairs have interchangeable roles. The first pair needs two seated people; every distinct subsequent pair needs at least one new person to sit. The construction attains that physical lower bound while keeping the chair roles fixed.

To compare with the original policy, charge its giver visits too. If every recipient stands after each tika, the eldest-first policy costs \{M+(N-1)\}e. Reusing recipient 1 across its final two giver blocks saves one episode for N\geq3, yielding (M+N-2)e for the same interaction order. The optimized order costs (M+1)e.

For N=10, these are 54, 53, and 46 total episodes, respectively. The two-seat restriction allows a modest improvement. The reduction to nine recipient episodes applies when giver movement has zero charged cost.

4.5 Everyone remains seated

With enough seats and access between every pair, all N people can sit at the start and stand at the end. Execute the M tikas sequentially while everyone stays in place. This costs Ne, which is optimal because each participant must be seated for at least one interaction. The arrangement assumes that distance and reach impose no extra standing requirements.

fig, ax = plt.subplots(figsize=(6.4, 4.4))
positions = {4: (-1.3, 1.05), 3: (1.3, 1.05), 2: (1.3, -1), 1: (-1.3, -1)}
for g, r in eldest_first(4):
    active = (g, r) == (4, 1)
    ax.annotate("", xy=positions[r], xytext=positions[g],
                arrowprops={"arrowstyle": "->", "shrinkA": 21, "shrinkB": 21,
                            "color": "#095c68" if active else "#bbc9d3",
                            "lw": 2.7 if active else 1.25,
                            "linestyle": "-" if active else "--"}, zorder=1)
for person, (x, y) in positions.items():
    seated_person(ax, x, y, person, "#087f72")
ax.text(0, 1.9, "All four people sit once", ha="center", fontsize=14, weight="bold")
ax.text(-2.15, .05, "4 → 1\nactive tika", ha="center", va="center", color="#095c68", fontsize=11)
ax.text(0, -2.05, "6 tikas · 4 seated episodes", ha="center", fontsize=12)
ax.set(xlim=(-2.85, 2.5), ylim=(-2.3, 2.2))
ax.axis("off")
fig.tight_layout()
export_figure(fig, "all-seated")

Figure 5: Four people remain seated for all six required interactions. Arrows mark older-to-younger dyads; the highlighted arrow shows a single active tika, 4 to 1. Each person has one seated episode, giving a total cost of 4e. This arrangement requires physical access between every pair.

5 A worked schedule

The cells below represent the same 15 interactions for six people. Numbers give their execution order. Giver blocks run along rows; recipient blocks run along columns. The altered order at block boundaries permits an occupant to remain seated.

fig, axes = plt.subplots(1, 3, figsize=(10.5, 3.5), constrained_layout=True)
for ax, name, fn in zip(axes, ["Eldest-first order", "Giver blocks", "Recipient blocks"],
                        [eldest_first, giver_blocks, recipient_blocks]):
    order = fn(6)
    matrix = np.full((6, 6), np.nan)
    for t, (g, r) in enumerate(order, 1):
        matrix[g - 1, r - 1] = t
    ax.imshow(matrix, cmap="Blues", vmin=0, vmax=30, origin="lower")
    for t, (g, r) in enumerate(order, 1):
        ax.text(r - 1, g - 1, str(t), ha="center", va="center", fontsize=10)
    g, r = episodes(order)
    ax.set(title=f"{name}\nG = {g}, R = {r}", xlabel="Recipient", ylabel="Giver",
           xticks=range(6), yticks=range(6), xticklabels=range(1, 7), yticklabels=range(1, 7))
    ax.spines[["top", "right"]].set_visible(False)
export_figure(fig, "interaction-orders")

Figure 6: Interaction order for six people. G and R count giver and recipient episodes with consecutive reuse. The specified reset-after-each-tika baseline would add one recipient episode to the first panel.

5.1 Inspect a schedule

The explorer charges every episode according to the selected cost model. The baseline includes its prescribed recipient reset after every tika.

People Episode costs Recipient only: giver 0, recipient 1 Two seats: each person 1 Giver 4, recipient 1 Giver 1, recipient 4 Schedule Optimal for these costs Eldest first, recipient resets Giver blocks, shared boundaries Recipient blocks, shared boundaries

Interaction

Complete interaction and entry list

Step	Giver	Recipient	New giver episode	New recipient episode

6 Verification and scope

The optimization is a sequence-dependent setup problem. One can represent each required interaction as a vertex, connecting two vertices when their interactions share the giver or share the recipient. The block constructions give a Hamilton path in this graph, so every transition changes just one role. Age gives a triangular set of allowed giver–recipient pairs, which makes the path construction particularly simple.

The following exact subset dynamic program independently checks the optimum for small N. Its state is a set of completed interactions and the final interaction; it considers every possible next interaction. The general proof above applies to every N\geq2.

from functools import lru_cache
from IPython.display import Markdown, display

for (_, _, illustrated), constructor in zip(
        dyad_examples, [eldest_first, recipient_blocks, giver_blocks]):
    assert illustrated == constructor(4)

def exact_cost(n, c_g, c_r):
    edges = eldest_first(n)
    full = (1 << len(edges)) - 1

    @lru_cache(None)
    def finish(mask, last):
        if mask == full:
            return 0
        g, r = edges[last]
        return min(c_g * (h != g) + c_r * (s != r)
                   + finish(mask | (1 << k), k)
                   for k, (h, s) in enumerate(edges) if not mask & (1 << k))

    return c_g + c_r + min(finish(1 << k, k) for k in range(len(edges)))

for n in range(2, 31):
    m = n * (n - 1) // 2
    for fn, counts in [(giver_blocks, (n - 1, m - n + 2)),
                       (recipient_blocks, (m - n + 2, n - 1))]:
        order = fn(n)
        assert len(order) == m and set(order) == set(eldest_first(n))
        assert episodes(order) == counts
        assert all(a[0] == b[0] or a[1] == b[1]
                   for a, b in zip(order, order[1:]))
        # Every person receives from all elders before giving to anyone younger.
        for person in range(2, n):
            assert max(t for t, (_, r) in enumerate(order) if r == person) < min(
                t for t, (g, _) in enumerate(order) if g == person)

checks = 0
for n in range(2, 6):
    m = n * (n - 1) // 2
    for c_g, c_r in [(0, 1), (1, 0), (1, 1), (4, 1), (1, 4)]:
        bound = (n - 1) * max(c_g, c_r) + (m - n + 2) * min(c_g, c_r)
        g, r = episodes(optimal_schedule(n, c_g, c_r))
        assert exact_cost(n, c_g, c_r) == c_g * g + c_r * r == bound
        checks += 1
display(Markdown(f"**{checks} exact optimization checks pass** for N = 2–5; "
                 "both constructions also pass coverage, cost, and age-precedence checks for N = 2–30."))

20 exact optimization checks pass for N = 2–5; both constructions also pass coverage, cost, and age-precedence checks for N = 2–30.

Several extensions change the optimization problem:

• Participant-specific discomfort. In the recipient-only model, costs e_j give optimum \sum_{j=1}^{N-1}e_j: seat every recipient once. With costs on both sides, minimizing the number of episodes alone can miss an important distributional objective.
• Fixed giver priority. Eldest-first giver blocks are preserved by the giver construction. Recipient batching allows younger givers to act before the eldest has finished all their tikas. Both implemented schedules ensure that each person receives from every elder before starting to give.
• Space and movement. A single recipient seat, a two-seat station, and a fully seated group have different feasible schedules. Reaching and walking costs need to be included when those actions are consequential.
• Parallel service or omitted dyads. Multiple simultaneous tikas introduce resource conflicts; incomplete family interaction graphs can eliminate the simple triangular construction. Those are different scheduling problems.

For the complete sequential ceremony, the cost model has an exact solution: batch the expensive role and retain one participant across each block boundary. The required social interactions are unchanged.