Loading [MathJax]/jax/output/HTML-CSS/jax.js

#37: Staircase Paths

Tagged as challenge, math

Written on 2018-02-10

Prerequisites

The symbol Zn denotes the set of all coordinate n-tuples with integer components. These are one kind of n-dimensional lattice.

Given two points s=(s1,,sn) and e=(e1,,en), their taxicab distance is se1:=ni=1|siei|.

Given a complex number z, we denote its normalization as N(z):={0if z=0,z/|z|otherwise.

Challenge

A staircase path between two points, informally, is any path by going only right or up.

Formally, given the starting point sZn and ending point eZn with se (i.e., each component of s is less than or equal to each corresponding component of e), a staircase path is a sequence of :=1+se1 coordinates σ0,,σ with the following facts:

  1. σ0=s,

  2. sσke (in the sense described above), and

  3. exactly one component of σk+1σk is 1, with the other n1 components equal to 0.

Denote the set of all staircase paths from s to e as {se}.

Part 1: Verify that facts 1–3 imply σ=e.

Next, consider the set Tm×n defined as n×m matrices whose entries are complex numbers of unit modulus. For consistency with the above, let's suppose the bottom-left element of each matrix is identified by (1,1) and top-right element is (n,m).

Part 2: Implement the function f:Tm×nT{0} defined by f(M):=N(Σ{(1,1)(m,n)}(x,y)ΣMx,y).

Extra Credit: Generalize f to work on a tensor of any order.


Unless otherwise credited all material copyright © 2010–2018 by Robert Smith