On the rod placement theorem of Rybko and Shlosman

摘要

Given n - 1 points x{sub}1 ≤ x{sub}2 ≤ ··· ≤ x{sub}(n-1) on the real line and a set of n rods of strictly positive lengths λ{sub}1 ≤ λ ≤ ··· ≤ λ{sub}n, we get to choose an n-th point x{sub}n anywhere on the real line and to assign the rods to the points according to an arbitrary permutation π. The rod λ{sub}(k) is thought of as the workload brought in by a customer arriving at time x{sub}k into a first in -first out queue which starts empty at -oo. If any x{sub}i equals x{sub}j for i < j, service is provided to the rod assigned to x{sub}i before the rod assigned to x{sub}j. Let Y{sub}π(x{sub}n) denote the set of departure times of the customers (rods). Let N{sub}π(x{sub}1,..., x{sub}(n-1); λ{sub}1,..., λ{sub}n) denote the number of choices for the location of x{sub}n for which 0 ∈ Y{sub}π(x{sub}n). Rybko and Shlosman proved that ∑N{sub}π(x{sub}1, x{sub}(n-1);λ{sub}1,...λ{sub}n ) = n! for Lebesgue almost all (x{sub}1,..., x{sub}(n-1);λ{sub}1,...λ{sub}n ). Let y{sub}π, k(x{sub}n) denote the departure point of the rod λ{sub}k. Let N{sub}π,k(y) denote the number of choices for the location of x{sub}n for which y{sub}π,k(x{sub}n) = y and let N{sub}k(y) = ∑{sub}π( N{sub}π, k(y). In this paper we prove that for every (x{sub}1,..., x{sub}(n-1);λ{sub}1,..., λ{sub}n) and every k we have N{sub}k(y) = (n - 1)! for all but finitely many y. This implies (and strengthens) the rod placement theorem of Rybko and Shlosman.