Introduction

First, the famous triangle constitued of binomial coefficient is a major breakthrough of mathematical sciences. Also, this triangle is useful in mathematics since it allows us to find each power (a + b) n of the sum of two real numbers a, b with the mean of the binomial coefficient formula. By the way, real numbers can commutate one with an other which is very practical in the daily life.

However, since the pionnering works in noncommutative algebras, we know that there is operators which do not commutate. For example, we know that the two main operators of the quantum mechanics, the momentum operator p = ∂ ∂x and the position operator q = x, form a noncommutative algebra with the defining relation [p, q] = 1 (0.1)

Moreover, we know that each function of C[x] can be develop by the serie expansion formula at a point a or x 0 . Next, varying this point a and replacing it with y, we can rewrite the serie expansion formula as :

f (x) = ∞ k=0 (-1) k k! (y -x) k ∂ k ∂y k f (y) (0.2)
In that case, observing this formula (0.2), we want to see the begining of a serie expansion. But the factor (y -x) k ∂ k ∂y k is not the same as ((y -x) ∂ ∂y ) k because those operators are noncommutative. Therefore, we decide to search a way to write the operator (y -x) k ∂ k ∂y k as a power of something. As a result, we find an equivalent of the binomial formula for this noncommutative algebra which we call Arm binomial formula and constitued the main result of this paper :

x ∂ ∂x n = n k=1 n k x k ∂ k ∂x k (0.3)
where appear a coefficient n k which is an equivalent of the binomial coefficient for this algebra. We give an expression for this Arm coefficient n k and this corresponding induction relation.

In fact the drawing of those Arm coefficient

+ 1 k + 1 = (k + 1) n k + 1 + n k (0.4)
Therefore, we use the Arm binomial formula to express the factor (y -x) k ∂ k ∂y k of (0.2) wich gives us the definition of the expansion serie of the Arm function.

In a first time, we expose the problem and we rewrite the serie expansion formula and give the goal of finding the Arm formula. In a second time, we give and show the Arm binomial theorem which is a strict equivalent of the binomial one and give somes examples. In a third time, we solve the problem in inversing the Arm binomial triangle and gives the defining equation of the Arm function. As examples, we give first series expansions powers of this function.

The Problem

First, we write the Taylor serie formula for the function f (x) at point a :

f (x) = ∞ k=0 (x -a) k k! lim x→a ∂ k ∂x k f (x) (1.1)
Instead of using the letter a, we choose to use the letter y, which give :

f (x) = ∞ k=0 (x -y) k k! lim x→y ∂ k ∂x k f (x) (1.2)
Here, ecause the limit of the derivative when x tend to y is the same as derivate by y, we can replace (1.2) by

f (x) = ∞ k=0 (x -y) k k! ∂ k ∂y k f (y) (1.3)
what we can also write as

f (x) = ∞ k=0 (-1) k k! (y -x) k ∂ k ∂y k f (y) (1.4)
Here we see that the begining of the sum seems to a serie expansion, but to have a serie expansion of the operator (y -x) ∂ ∂y , we need to find how to convert (y -x) k ∂ k ∂y k in ((y -x) ∂ ∂y ) k . We can easily guess that this is the same problem as converting

y k ∂ k ∂y k in (y ∂ ∂y ) k .
Then this is the purpose of this paper to find the serie expansion of the Arm function A(X) such that

f (x) = A (y -x) ∂ ∂y f (y) (1.5)
with its series expansion

A(X) = ∞ k=0 α k X k (1.6)
and finally identify

A (y -x) ∂ ∂y = ∞ k=0 (-1) k k! (y -x) k ∂ k ∂y k (1.7)
2 The Arm Binomial Theorem

First, we introduce the Arm binomial coefficient and the corresponding Arm triangle.

Proposition 1. The element of the Arm triangle is such that

n + 1 k + 1 = (k + 1) n k + 1 + n k (2.8)
and we have the definition of the Arm binomial coefficient :

n k = 1 k! k p=1 k p (-1) p-k p n (2.9)
where n k is the binomial coefficient. Proof : We show by induction that the only element which respect (2.8) is the sequence (2.9 : Basic :

1 1 = 1 1! 1 p=1 1 p (-1) p-1 p 1 = 1 (2.10)
Inductive step : We suppose the relation

n k = 1 k! k p=1 k p (-1) p-k p n (2.11)
for all k ∈ [1, n] and we show that the relation

n + 1 k = 1 k! k p=1 k p (-1) p-k p n+1 (2.12) is true for all k ∈ [1, n + 1].
So the relation we have to respect is

n + 1 k + 1 = (k + 1) n k + 1 + n k (2.13)
Using the induction hypothesis, we have :

n + 1 k + 1 = (k + 1) 1 (k + 1)! k+1 p=1 k + 1 p (-1) p-k-1 p n + 1 k! k p=1 k p (-1) p-k p n (2.14)
and we obtain

n + 1 k + 1 = 1 k! k+1 p=1 k p + k p -1 (-1) p-k-1 p n + k p=1 k p (-1) p-k p n (2.15) since the binomial coefficient relation is true n+1 k = n k + n k-1 . The relation (2.15) becomes n + 1 k + 1 = 1 k! k+1 p=1 k p -1 (-1) p-k-1 p n (2.16)
Using the fact that k+1 p = k+1 p k p-1 , we obtain

n + 1 k + 1 = 1 k! k+1 p=1 p k + 1 k + 1 p (-1) p-k-1 p n (2.17)
which is what we want to show :

n + 1 k + 1 = 1 (k + 1)! k+1 p=1 k + 1 p (-1) p-k-1 p n+1 (2.18)
Since both the basis and the inductive step have been performed, by mathematical induction, the statement holds for all natural n. Q.E.D.

Here we give the first twelfth lines of the Arm triangle constitued by the Arm coefficients n k 1≤k≤n≤12 . Here you can easily check the validity of the induction relation (2.8) :

k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10 k = 11 k = 12 n = 1 n = 2 1 n = 3 3 1 n = 4
n + 1 k + 1 = (k + 1) n k + 1 + n k (2.19)
As an example, we try it with n = 5 and k = 3

5 3 = 3 4 3 + 4 2 25 = 3 × 6 + 7 (2.
n k = 1 k! k p=1 k p (-1) p-k p n (2.22)
As an example, we try it with n = 5 and k = 3 :

5 3 = 1 3! 3 p=1 3 p (-1) p-3 p 5 5 3 = 1 6 3 1 1 5 - 3 2 2 5 + 3 3 3 5 25 = 1 6 3 × 1 5 -3 × 32 + 1 × 243
(2.23)

As an other example, we try it with n = 8 and k = 4 :

8 4 = 1 4! 4 p=1 4 p (-1) p-4 p 8 8 4 = 1 24 - 4 1 1 8 + 4 2 2 8 - 4 3 3 8 + 4 4 4 8 1701 = 1 24 -4 × 1 8 + 6 × 256 -4 × 6561 + 1 × 65536 (2.24)
Now, we introduce the Arm binom theorem Theorem 1. The Arm binomial theorem is given by

x ∂ ∂x n = n k=1 n k x k ∂ k ∂x k (2.25)
where n k is the Arm binomial coefficient (2.9).

Proof :

We show the relation (2.25) by induction. Basic :

x ∂ ∂x 1 = 1 k=1 1 k x k ∂ k ∂x k (2.26)
Inductive step :

We suppose that the relation

x ∂ ∂x n = n k=1 n k x k ∂ k ∂x k (2.27)
is true at the n-th step. Furthermore, we show that the relation

x ∂ ∂x n+1 = n+1 k=1 n + 1 k x k ∂ k ∂x k (2.28)
for the n + 1-th step.

x ∂ ∂x n+1 = x ∂ ∂x x ∂ ∂x n 7
Using the induction hypothesis, we have

x ∂ ∂x n+1 = x ∂ ∂x n k=1 n k x k ∂ k ∂x k = n k=1 n k x ∂ ∂x x k ∂ k ∂x k = n k=1 n k x kx k-1 ∂ k ∂x k + x k ∂ k+1 ∂x k+1 = n k=1 k n k x k ∂ k ∂x k + n k=1 n k x k+1 ∂ k+1 ∂x k+1 = n k=1 k n k x k ∂ k ∂x k + n+1 k=2 n k -1 x k ∂ k ∂x k = n+1 k=1 k n k + n k -1 x k ∂ k ∂x k x ∂ ∂x n+1 = n+1 k=1 n + 1 k x k ∂ k ∂x k (2.29)
Since both the basis and the inductive step have been performed, by mathematical induction, the statement holds for all natural n. Q.E.D.

We can check the validity of this theorem for the first line :

x ∂ ∂x 1 = 1 × x ∂ ∂x (2.30)
for the second line :

x ∂ ∂x 2 = x ∂ ∂x x ∂ ∂x 1 x ∂ ∂x 2 = 1 × x ∂ ∂x + 1 × x 2 ∂ 2 ∂x 2 (2.31)
for the third line :

x ∂ ∂x 3 = x ∂ ∂x x ∂ ∂x 2 x ∂ ∂x 3 = x ∂ ∂x x ∂ ∂x + x 2 ∂ 2 ∂x 2 x ∂ ∂x 3 = 1 × x ∂ ∂x + 3 × x 2 ∂ 2 ∂x 2 + 1 × x 3 ∂ 3 ∂x 3 (2.32)
and for the fourth line :

x ∂ ∂x 4 = x ∂ ∂x x ∂ ∂x 3 x ∂ ∂x 3 = x ∂ ∂x x ∂ ∂x + 3x 2 ∂ 2 ∂x 2 + x 3 ∂ 3 ∂x 3 x ∂ ∂x 3 = 1 × x ∂ ∂x + 7 × x 2 ∂ 2 ∂x 2 + 6 × x 3 ∂ 3 ∂x 3 + 1 × x 4 ∂ 4 ∂x 4
(2.33) etc

Resolution Of The Problem

To solve our problem we need to know how converting

x k ∂ k ∂x k in (x ∂ ∂x ) k .
Proposition 2. The inverse Arm Binomial theorem is given by

x n ∂ n ∂x n = n k=1 n k -1 x ∂ ∂x k (3.34)
where the inverse if the Arm triangle is define with the induction relation

n + 1 k + 1 -1 = -n n k + 1 -1 + n k -1 (3.35)
with the definition of the comatrice of cofactors and each p ∈ N.

Proof : We show (3.34) by induction Basic :

x 1 ∂ 1 ∂x 1 = 1 k=1 1 k -1 x ∂ ∂x k (3.36)
Inductive step : We suppose the relation

x n ∂ n ∂x n = n k=1 n k -1 x ∂ ∂x k (3.37)
for all k ∈ [1, n] and we show that the relation

x n+1 ∂ n+1 ∂x n+1 = n+1 k=1 n + 1 k -1 x ∂ ∂x k (3.38) is true for all k ∈ [1, n + 1].
We have the relation

∂ ∂x x n ∂ n ∂x n = nx n-1 ∂ n ∂x n + x n ∂ n+1 ∂x n+1 (3.39)
and so

x n+1 ∂ n+1 ∂x n+1 = x ∂ ∂x x n ∂ n ∂x n -nx n ∂ n ∂x n (3.40)
Using the induction hypothesis, we have :

x n+1 ∂ n+1 ∂x n+1 = x ∂ ∂x n k=1 n k -1 x ∂ ∂x k -n n k=1 n k -1 x ∂ ∂x k x n+1 ∂ n+1 ∂x n+1 = n k=1 n k -1 x ∂ ∂x k+1 -n n k=1 n k -1 x ∂ ∂x k x n+1 ∂ n+1 ∂x n+1 = n+1 k=2 n k -1 -1 x ∂ ∂x k -n n k=1 n k -1 x ∂ ∂x k x n+1 ∂ n+1 ∂x n+1 = n+1 k=1 n k -1 -1 -n n k -1 x ∂ ∂x k x n+1 ∂ n+1 ∂x n+1 = n+1 k=1 n + 1 k -1 x ∂ ∂x k
Since both the basis and the inductive step have been performed, by mathematical induction, the statement holds for all natural n. Since both the basis and the inductive step have been performed, by mathematical induction, the statement holds for all natural n.

Here we give the first tenth lines of the inverse Arm triangle n k -1 Now to solve our main problem, we take back the equation (1.4)

1≤k≤n≤10 : k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10 n = 1 1 0 0 0 0 0 0 0 n = 2 -1 1 0 0 0 0 0 0 0 0 n = 3 2 -3 1 0 0 0 0 0 0 0 n = 4 -6 11 -6 1
f (x) = ∞ k=0 (-1) k k! (y -x) k ∂ k ∂y k f (y) (3.41)
and using (3.34), we obtain

f (x) = f (y) + ∞ k=1 (-1) k k! k i=1 k i -1 (y -x) ∂ ∂y i f (y) (3.42)
which we can write as

f (x) = 1 + ∞ k=1 k i=1 (-1) k k! k i -1 (y -x) ∂ ∂y i f (y) (3.43)
Finally, we can see a definition of the Arm function

A(X) = 1 + ∞ k=1 k i=1 (-1) k k! k i -1 X i (3.44)
which as serie expansion

k = 0 A(X) = 1 k = 1 A(x) = 1 -X k = 2 A(x) = 1 -1 2 X + 1 2 X 2 k = 3 A(x) = 1 -1 3 X + 1 2 X 2 -1 6 X 3 k = 4 A(x) = 1 -1 4 X + 11 24 X 2 -1 4 X 3 + 1 24 X 4 k = 5 A(x) = 1 -1 5 X + 5 12 X 2 -7 24 X 3 + 1 12 X 4 -1 120 X 5 k = 6 A(x) = 1 -1 6 X + 137 360 X 2 -5 16 X 3 + 17 144 X 4 -48 X 5 + 1 720 X 6
4 Binomial Groups And Algebras

We first define the binomial algebra Proposition 3. We define the binomial algebra which gives the definition of the translation group

((x + t) k ) 0≤k≤n = exp(t.b n )(x k ) 0≤k≤n (4.45)
where b n is the binomial algebra defined by :

(b n ) i+1,i = i (4.46)
and zero elsewhere or

b n =        1 2 . . . n -1        (4.47)
Proof : The matrice n-1 k 0≤k≤n-1 is given by : 

      1 0 0 . . . 1 1 0 . . . 1 2 1 0 . . . . . . . . . . . . n-1 0 n-1 1 . . . n -1 1        (4.48)
We take the t-th power of n-1 k 0≤k≤n-1 :

       1 0 0 . . . 1t 1 0 . . . 1t 2 2t 1 0 . . . . . . . . . . . . n-1 0 t n-1 n-1 1 t n-2 . . . (n -1)t 1        (4.49) which we call n-1 k t 0≤k≤n .
Here we see that

((x + t) k ) 0≤k≤n-1 = n -1 k t 0≤k≤n-1 (x k ) 0≤k≤n-1 (4.50)
Then we see that the corresponding algebra of n-1 k 0≤k≤n-1 is

b n = lim t→0 ∂ ∂t n -1 k t 0≤k≤n-1 =        1 2 . . . n -1        (4.51) So we can deduce that exp(tb n ) = n-1 k t 0≤k≤n-1 and exp(-tb n ) = n-1 k -t 0≤k≤n
Example : for n = 4, we have

exp(t.b 4 ) = exp     t     0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0         =     0 0 0 0 1t 0 0 0 0 2t 0 0 0 0 3t 0     0 +     0 0 0 0 1t 0 0 0 0 2t 0 0 0 0 3t 0     1 + 1 2!     0 0 0 0 1t 0 0 0 0 2t 0 0 0 0 3t 0     2 + 1 3!     0 0 0 0 1t 0 0 0 0 2t 0 0 0 0 3t 0     3 exp(t.b 4 ) =     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1     0 +     0 0 0 0 1t 0 0 0 0 2t 0 0 0 0 3t 0     + 1 2     0 0 0 0 0 0 0 0 2t 2 0 0 0 0 6t 2 0 0     + 1 6     0 0 0 0 0 0 0 0 0 0 0 0 6t 3 0 0 0     So we find that exp(t.b 4 ) =     1 0 0 0 1t 1 0 0 1t 2 2t 1 0 1t 3 3t 2 3t 1     (4.52) and thus     (x + t) 0 (x + t) 1 (x + t) 2 (x + t) 3     =     1 0 0 0 t 1 0 0 t 2 2t 1 0 t 3 3t 2 3t 1         x 0 x 1 x 2 x 3     (4.53)
Then we define the Arm binomial algebra Proposition 4. We define the Arm binomial algebra as

x ∂ ∂x k 0≤k≤n = exp (a n ) x k ∂ k ∂x k 0≤k≤n (4.54)
where a n is the binomial algebra defined by :

a n = lim t→0 ∂ ∂t n k t 0≤k≤n (4.55)
and zero elsewhere or

a n =        1 -1 2 3 1 2 -2 6 . . . . . . . . . . . .        (4.56) Proof : Admitted Example : for n = 4, we have exp(t.a 4 ) = exp     t     0 0 0 0 1 0 0 0 -1 2 3 0 0 1 2 -2 6 0         =     0 0 0 0 1t 0 0 0 -1 2 t 3t 0 0 1 2 t -2t 6t 0     0 +     0 0 0 0 1t 0 0 0 -1 2 t 3t 0 0 1 2 t -2t 6t 0     1 + 1 2!     0 0 0 0 1t 0 0 0 -1 2 t 3t 0 0 1 2 t -2t 6t 0     2 + 1 3!     0 0 0 0 1t 0 0 0 -1 2 t 3t 0 0 1 2 t -2t 6t 0     3 exp(t.a 4 ) =     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1     0 +     0 0 0 0 1t 0 0 0 -1 2 t 3t 0 0 1 2 t -2t 6t 0     + 1 2     0 0 0 0 0 0 0 0 3t 2 0 0 0 -5t 2 18t 2 0 0     + 1 6    
     x ∂ ∂x 0 x ∂ ∂x 1 x ∂ ∂x 2 x ∂ ∂x 3      =     1 0 0 0 1 1 0 0 1 3 1 0 1 7 6 1          x 0 ∂ 0 ∂x 0 x 1 ∂ 1 ∂x 1 x 2 ∂ 2 ∂x 2 x 3 ∂ 3 ∂x 3      (4.60)      x 0 ∂ 0 ∂x 0 x 1 ∂ 1 ∂x 1 x 2 ∂ 2 ∂x 2 x 3 ∂ 3 ∂x 3      =     1 0 0 0 -1 1 0 0 2 -3 1 0 -6 11 -6 1          x ∂ ∂x 0 x ∂ ∂x 1 x ∂ ∂x 2 x ∂ ∂x 3      (4.61)

Conclusion

In the third section, we do not give a formal expression for the inverse n k -1 of the Arm triangle.

We just define it with the definition of the comatrix of cofactors. Maybe in a future version, we will find a mathematical expression for this coefficient.

In fact, the inverse of the usual binomial triangle also exists but it is not interesting to study it since it is the same as the binomial triangle with an additional minus.

  20)As an other example, we try n = 8 and k = we check the validity of the relation (2.9) :

  -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1

Figure 1 -

 1 Figure 1 -The Arm function for k = 6 and k = 7


O Marchal

Locks and keys: How fast can you open several locks with too many keys?

Keywords: while LocksRemaining>0 do LockChosen, =rand(LocksRemaining)()+1, KeyChosen, =rand(KeysRemaining)()+1, if LockChosen=KeyChosen then LocksRemaining, =LocksRemaining-1, KeysRemaining, =KeysRemaining-1, fi

This short note is the result of a French "Hippocampe internship" 2 that aims at introducing the world of research to young undergraduate French students. The problem studied is the following: imagine yourself locked in a cage barred with n different locks. You are given a keyring with N ≥ n keys containing the n keys that open the locks. In average, how many trials are required to open all locks and get out? The article studies 3 different strategies and compare them. Implementation of the strategies are also proposed as illustrations of the theoretical results.

Statement of the problem

The precise statement of the problem and the various assumptions are the following:

Statement of the problem:

We need to open n locks with a keyring containing N ≥ n keys. We are interested in determining the average and the standard deviation of the number of trials to open all locks. The special case when the number of keys equals the number of locks (n = N ) is included.

Assumptions:

The following assumptions about locks and keys are made:

• All locks and keys are assumed to be indistinguishable.

• All locks are different and require a specific key to be opened.

• A lock can always be opened, i.e. the key required to open it belongs to the keyring.

• A key cannot open more than one lock.

Consequently, the keyring contains the n different keys corresponding to the locks as well as additional keys that do not open anything when N > n. The keys are randomly placed in the keyring. We denote by T n,N the number of trials to open all locks. We are interested in gathering as much information as possible on T n,N especially E(T n,N ) and Var(T n,N ).

Strategy 1: The totally random strategy

The first strategy one can think of is to select randomly one of the remaining keys and try it randomly into one the remaining locks to open. In particular we do not keep track about the previous tries except for the fact that we discard locks that are already opened and their corresponding keys. Let us introduce X i (1 ≤ i ≤ n) the number of trials required between the opening of i -1 th lock and the i th lock. (for i = 1, X 1 is just the number of trials required to open the first lock). Thus, we have:

T n,N = n i=1 X i (2.1)
In this strategy, the variables X i are obviously independent since we do not keep track of the history of the trials. To open the i th lock, we choose randomly into the N -i + 1 remaining keys. Therefore we get:

∀ k ≥ 1 : P (X i = k) = k-1 i=1 N -i N -i + 1 1 N -i + 1 = N -i N -i + 1 k-1 1 N -i + 1 (2.2)
Thus we observe that X i is distributed as a geometric variable with parameters

q i = N -i N -i+1
. This is of course coherent with the fact that the strategy is memory-less. It is then straightforward to obtain the mean and standard deviation of X i :

E(X i ) = N -i + 1 and Var(X i ) = (N -i)(N -i + 1) (2.3)
Since the variables X i are independent, we get from (2.1) that:

E(T n,N ) = n i=1 E(X i ) = n(2N -n + 1) 2 and Var(T n,N ) = n i=1 Var(X i ) = n(3N 2 -3N n + n 2 -1) 3 (2.4)
In the case when N = n, we get:

E(T n,n ) = n(n + 1) 2 and Var(T n,n ) = n(n -1)(n + 1) 3 (2.5)
Simulations (See 6) show that T n,N is very well approached by a Γ distribution with parameters

Γ k = 3n(2N -n+1) 2 4(3N 2 -3N n+n 2 -1) , θ = 2(3N 2 -3N n+n 2 -1)

3(2N -n+1)

. Parameters have been adjusted here so that expectation and standard deviation match (we recall that E(Γ(k, θ)) = kθ et V ar(Γ(k, θ)) = kθ 2 ). Appearance of the Γ distribution is not surprising here. Indeed, geometric variables are a discrete version of the exponential distribution (typical of memory-less phenomenon) that is a special case of Γ distributions (k = 1). Additionally, the sum of independent Γ distributions with parameters

(k i , θ) is known to remain a Γ distribution with parameters k = n i=1
k i , θ . However note that our parameters θ i are different so that the last theorem cannot be applied properly but only in an approximate manner.

Of course, the totally random strategy is not the optimal strategy since we do not keep track of the combinations tried previously. These strategies are developed in the next sections.

3 Strategy 2: Take a lock and test all keys Strategy: The strategy is now the following: we choose a lock and then we try all remaining (that is to say all keys except those that have already opened a lock) keys successively until we find the (unique) right key that opens the lock. Then we continue with the next lock by starting over with the first remaining key and so on until all are opened.

Remark: Since a key opens at most one lock, we can discard the successful keys. Moreover when a lock is opened, all remaining keys (including those that have been tried and those that have not been tried on the lock) remain equivalent for the next locks. Indeed, since we now that a lock is exactly opened by one key, we get that when a lock is opened, all keys that have not been tried immediately acquire the property that they do not open this lock, a property that was already known for the keys that have been tried on the lock. In particular the way we will order the keys for the next lock does not affect the distribution of the number of trials.

As in the previous section, let X i (1 ≤ i ≤ n) be the number of trials required between the opening of i -1 th lock and the i th lock. (for i = 1, X 1 is just the number of trials required to open the first lock). Equation (2.1) still holds. Moreover from the previous remark, we get that the variables X i are still independent. To open the i th lock, only N + 1 -i keys remain and we get for 1 ≤ k ≤ N + 1 -i:

P (X i = k) = N -i N + 1 -i N -i -1 N -i . . . N + 1 -i -k N + 2 -i -k 1 N + 1 -i -k = 1 N + 1 -i (3.1)
Consequently we observe that X i follows a discrete uniform distribution:

X i ∼ Uniform ({1, . . . , N -i + 1}) (3.2)
In the end we get:

E(X i ) = N + 2 -i 2 and Var(X i ) = (N + 2 -i)(N -i) 12 (3.3)
and eventually

E(T n,N ) = n(2N + 3 -n) 4 and Var(T n,N ) = n(6N 2 -6N n + 6N + 2n 2 -3n -5) 72 (3.4)
In the case when N = n we get:

E(T n,n ) = n(n + 3) 4 and Var(T n,n ) = n(2n + 5)(n -1) 72 (3.5)
Simple computations shows that this strategy is in average better than the totally-random one even in the case when N = n. Simulations (See section 6) of this strategy are also in agreement with the theoretical results.

Strategy 3: Take a key and try it in all locks

Strategy: We now consider the following strategy: we take a key and we try it into all remaining locks. We stop when it opens a lock or when we have exhausted all remaining locks. We then take the next key and start over with the first remaining lock and so on until all locks are opened.

Let us denote as before X i (1 ≤ i ≤ n) the number of trials required between the opening of i -1 th lock and the i th lock. (for i = 1, X 1 is just the number of trials required to open the first lock) so that equation (2.1) still holds. In this situation, the variables X i are no longer independent. Indeed, let us assume that to open the first lock, we have used all N -n useless keys (keys that do not open any locks), then it is now impossible that X 2 is greater than n -1 since we only have n -1 keys and n -1 locks remaining. On the contrary, if the first key opens a lock (that is X 1 ≤ n), then X 2 may be strictly greater than n if we choose a useless key. Hence we see that the range of X 2 depends on the result of X 1 , thus X 1 and X 2 cannot be independent. The case N = n appears to be singular, since in that case the variables X i remain independent (since a key must open a lock). Determining the distribution of X i is more challenging too. Indeed X p = k depends on the number of keys that have been discarded until the opening of the p -1 th lock. More specifically, if l locks have been opened before the trial of the p th key, then the key opening lock p must be in position k + l in the keyring. Consequently we get:

P (X p = k) = 1 N p-1 l=0 k+l-1 l N -k-l p-1-l N -1 p-1 (4.1)
We want to prove the following: Proposition 4.1 The following identity holds:

1 N p-1 l=0 k+l-1 l N -k-l p-1-l N -1 p-1 = 1 N -p + 1 , ∀ k ≤ N -p + 1 (4.2)
Proof: This identity is a consequence of the Chu-Vandermonde identity3 :

∀ J ≤ K ≤ N : N + 1 K + 1 = K m=0 m J N -m K -J (4.3)
Then replacing N by N -1 and using the symmetry of the binomial coefficients we get to:

∀ J ≤ K ≤ N -1 : N N -K -1 = K m=0 m J N -1 -m K -J (4.4)
Taking K = N -p and J = k -1 we find

∀ k ≤ N -p + 1 : N p -1 = p+k-2 m=k-1 m k -1 N -1 -m N -p -k + 1 (4.5)
where we restrict the sum so that only non-zero binomial coefficients are present. Performing the change l = m -k + 1 gives:

p-1 l=0 k + l -1 k -1 N -k -l N -k -p + 1 = N p -1 = N N -p + 1 N -1 p -1 , ∀ k ≤ N -p + 1 (4.6)
This last equality is then equivalent to proposition 4.1.

From proposition 4.1 we conclude that the variable X p is distributed like a discrete uniform distribution:

X i ∼ Uniform ({1, . . . , N + 1 -i}) (4.7)
Expectation and standard deviation are then straightforward to compute:

E(X i ) = (N + 2 -i) 2 and Var(X i ) = (N + 2 -i)(N -i) 12 (4.8)
From (2.1) we finally get:

E(T n,N ) = n i=1 (N + 2 -i) 2 = n(2N -n + 3) 4 (4.9)
We recover the same result as in the previous strategy (3.4). In particular T n,N is still the sum of uniform variables. However in this approach, it is unclear to see why the variables X i should be uncorrelated. Consequently the computation of the variance is not directly possible except for the case N = n where the variable X i are independent and (3.5) is recovered.

The last result indicates that the last two strategies seem similar since their results are identical. However computations the last strategy seem much more complicated than for the previous one and fails to explain why the strategy are equivalent. In fact, the last two strategies are exactly equivalent no matter the order of keys selected: they will provide exactly the same number of trials for any initial conditions. We will prove this result in the next section using a combinatorial one-to-one correspondence.

Equivalence of strategies 2 and 3

Let us order the locks from 1 to n and number the keys that open a lock with their corresponding lock number. The useless keys are then numbered randomly from n+1 to N (the number itself is of no interest, the only piece of information that we need is that it does not open anything). Then an initial condition corresponds to the choice of a random permutation of {1, . . . , N } of the keys. More specifically, the randomness of the problem consists in drawing a random permutation of {1, . . . , N } uniformly on the symmetric group S N (with N ! possibilities). As soon as the permutation is given (i.e. the order of the keys given) then the number of trials is completely determined using one of the strategies developed in sections 3 or 4. This defines properly the probability space on which we work on. Let us illustrate the situation on the following example: For both strategies, it is easy to prove that the only boxes tried in the previous strategies are those being on the left and at the top of a ticked box. Indeed:

1. In strategy developed in section 3, boxes at the right of a ticked box will be discarded because we do not try the remaining keys as soon as a lock is open. Boxed below a ticked box will not be tried because as soon as a lock is opened, we do not test any other key on it.

2. In strategy developed in section 4, boxes at the right of a ticked box will be discarded because as soon as a lock is opened we do not test any other key on it. Boxes below a ticked box will not be tried because as soon as a key has opened a lock, we do not try it on any other lock (since we know from the assumptions that it can at most open one lock).

Hence figures 1 and 2 show that for any initial condition, the number of trials T n,N will be the same for both strategies: only the order of the various tries will differ in the two strategies.

Numeric simulations

Numeric simulations can be carried out to illustrate the various strategies. We present here the code in Maple as well as histograms of the distributions of T n,N for different values of n and N . All strategies require a procedure to generate a random permutation:

RandomPerm:=proc(n) local T: T:=[seq(1..n)]: return(Shuffle(T)): end proc:
Then, the totally random strategy can be implemented like: One can obviously observe that the theoretical results are in perfect agreement with the simulations. Contrary to the totally random case, T n,N is better approximated with a classical normal distribution in the other two strategies at least when n is large enough. This is quite logical since it seems reasonable that a Central Limit Theorem may be applied for equation (2.1).

Conclusion and Outlooks

Though the problem can be easily stated and understood by common people (after inquiries, this was one of the points that seduced the students to choose this problem among others), its resolution presents various levels of mathematics from elementary ones (small values of n and N , totally random strategy) to more involved ones (Chu-Vandermonde identity). The problem is also well suited for simulations and implementation even for students with basic notions of programming. Basic statistical skills are also required to represent the results of simulations. Retrospectively, in addition to the Chu-Vandermonde identity and its connection to the problem, the hardest part for students (even with help) was to unravel the equivalence presented in figure 2.

The problem raises numerous questions and possible developments:

• What happens if a key is allowed to open more than one lock? Does it affect the order in which we start over when a lock is opened? What happens if some locks are allowed to be the same?

• For low n and N , it seems possible to get the complete probability distribution of T n,N .

• Simulations in the totally random case indicates that the distribution of T n,N should be close to a Γ distribution and arguments where presented to explain this observation. Can these arguments be precised and a complete proof given?

• When n is large, simulations shows that the distribution of T n,N approaches a normal distribution. Equation (2.1) provides a perfect setting to apply some Central Limit Theorem. Can we have a detailed proof of the application of the CLT and a bound relatively to the error committed in the approximation?

• Illustration provided by figure 2 shows that the problem can be recast into a combinatorial problem of counting top-left boxes after selecting some at random (imposing one per line). Hence it would not be surprising that our problem is equivalent to another one in a totally different setting in relation with random permutations.

• In this article we presented the more natural strategies that come to mind, but are the strategies presented here really the optimal strategies to minimize in average T n,N ?

• In real life, changing locks may be more time-consuming than changing keys if the locks are located far apart. Conversely, the keyring might be hard to handle so that changing from a key to the next one may be complicated. Hence one could introduce different times when changing keys or locks. Are the results presented here globally unchanged?

Fig. 1 :

 1 Fig. 1: Illustration of the strategy developed in section 3 when locks 1 up to 5 are opened respectively by keys in position 3, 5, 2, 9, 7 in the keyring.

Fig. 2 :

 2 Fig. 2: Illustration of the strategy developed in section 4 when locks 1 up to 5 are opened respectively by keys in position 3, 5, 2, 9, 7 in the keyring. Boxes ticked in red indicate the position of the keys in the keyring.

  RandomStrategy:=proc(NumberKeys,NumberLocks) local NumberTrials, LocksRemaining, KeysRemaining, LockChosen, KeyChosen: NumberTrials:=0: LocksRemaining:=NumberLocks:

Fig. 3 :Fig. 4 :Fig. 5 :Fig. 6 :

 3456 Fig. 3: Illustration of the totally random strategy in the case n = N = 8. Curve in red represents the Γ distribution with the theoretical parameters. Curve in black represents the Γ distribution with parameters inferred from the simulation

"Hippocampe" (sea-horse or hippocampus in French) internships are three days sessions during which small groups of students specialized in mathematics and physics are presented with a problem that they have to solve under the supervision of an academic professor.

The Chu-Vandermonde identity can be proved easily by identification of the order x N +1 in the binomial expansion of the identity(1 + x) N +m = (1 + x) N (1 + x) m

The strategy developed in section 4 can be implemented like: A similar code can be implemented for strategy developed in section 3. Results of the simulations and comparison with the theoretical results are: