All starting points

This is an extension of a classic puzzle.

You have a circular road, with $n$ petrol bunks (or gas stations as called in America) located somewhere along the road. You are given the length of each segment of the road, which is between two petrol bunks. You are also given the amounts of petrol left in each bunk. You are also told that the total amount of petrol is just enough to complete exactly one lap of the circular road, using a car that starts with an empty tank. The car has infinite capacity and you fill whatever you can when you reach a petrol bunk.

Now given a car with an empty tank, you need to find out in $O(n)$ time, all the possible starting points which will allow you to complete the lap. [The classic puzzle was to prove that there is a such a starting point].

The petrol bunks are numbered $1$ to $n$, and you are given an array $p[1, \dots, n]$ of the amounts of petrol, and a distance array $d[1, \dots, n]$ of the distances between the petrol bunks ($d[i] = $ distance between $p[i]$ and $p[i+1]$). The output will be a list of numbers between $1$ and $n$, denoting the petrol bunks you can start at.

Assume that one unit of petrol covers exactly one unit of distance.

[Solution]

Four Numbers Game II

In an earlier post a question was left open. I will repeat the question here.

You start with $n$ integers $a_1, a_2, \dots, a_n$ and in one step you perform the following transformation

$$(a_1, a_2, \dots , a_n) \to (|a_1-a_2|, |a_2 - a_3|, \dots, |a_{n-1} - a_n|, |a_n - a_1|)$$

($|x| = $ absolute value of $x$)

You keep performing this operation till all the numbers become zero.

Find all $n \gt 1$ (with proof), such that no matter which integers you start with, the numbers eventually become zero.

Opening Lead problem

This is a hand from a recent regional in Lynwood, WA (near Seattle).

Playing a knockout game,  you hold JTx, Kxxx, xx, Jxxx, white vs red.

LHO is dealer and opens 1S. Partner overcalls 2H, RHO bids 3D. You bid 3H, LHO bids 4D, partner bids 4H, and opponents buy the contract in 5D (the auction is as I remember, it might have been different at the table).

What would you lead?



You probably led a heart? If so, hope you had led the HK!

These were the four hands (you are west)

IMPS N/S	North ♠ Axxxxx ♥ T ♦ Txxx ♣ AQ
West ♠ JTx ♥ Kxxx ♦ xx ♣ Jxxx		East ♠ KQ ♥ AQJxx ♦ xx ♣ KTxx
	South ♠ xx ♥ xxx ♦ AKQJx ♣ xxx

W	N	E	S
	1S	2H	3D
3H	4D	4H	5D
P	P	P

If you lead a low heart, declarer can make the contract by setting up the spades. Partner cannot attack clubs.

If you lead the HK, you can hold the lead and switch to a club, establishing your club trick before declarer can set up spades, and the contract goes down one.

A club lead would have worked too.

Leading the HK is "standard" with that hand, and I believe most advanced players would find it.

Span sums [Solution]

The problem was here.

In short, compute the total of the spans for each sub-array of a given array, the span of an array being the difference between the maximum and minimum element of the array.

Solution

---

Note that it is enough to figure out the sum the maximum elements of each array [and minimum, and then take the difference].

Suppose we want to find the max sum of sub-arrays of an array $A[1,\dots,n]$, and the maximum element of $A$ appears at $A[M]$. Assume the elements are distinct for now, but does not really matter.

Now $A[M]$ is the maximum of any subarray $A[i,\dots,j]$ where $i \le M \le j$ and thus contributes $A[M]\times M \times (n-M+1)$ to the total we seek.

Now we recursively compute the totals for $A[1,\dots,M-1]$ and $A[M+1,\dots,n]$ and add all those up.

This can be done in $O(n)$ time, if we compute the cartesian tree corresponding to the array (which can be done in $O(n)$ time).

The cartesian tree is basically a max-heap whose inorder traversal gives back the array in the order $A[1], A[2], \dots$. The whole tree corresponds to $A[1, \dots, n]$, while the left subtree of the root corresponds to $A[1, \dots, M-1]$ and the right sub-tree corresponds to $A[M+1, \dots, n]$.

In order to get past the distinctness assumption, we can work with $B[i] = (A[i], i)$ instead.

[See: http://ruffnsluff.blogspot.com/2015/05/max-area-in-histogram-solution.html for an explanation of Cartesian trees. There is a diagram too!]

Prime binomial sum [Solution]

The problem was to show that

$$ \sum_{k=1}^{\lfloor 2p/3 \rfloor} \binom{p}{k}$$

is divisible by $p^2$ for a prime $p \ge 5$.

Solution

---

Now working in the field $F_p$  (where division makes sense) we have that

$$ \frac{\binom{p}{k}}{p} = \frac{(p-1)!}{k! (p-k)!}  = \frac{(p-1)(p-2)\dots(p-k+1)}{k!}$$

$$ = \frac{(-1)(-2)\dots(-(k-1))}{k!} = \frac{(-1)^{k-1}}{k}$$


Let $ T = {\lfloor 2p/3 \rfloor}, U = \lfloor \frac{T}{2} \rfloor$

Thus the sum we need to show divisible by $p$ (note that we divided by $p$ already) is

$$\sum_{k=1}^{T} \frac{(-1)^{k-1}}{k}$$


$$ =  \sum_{k=1}^{T} \frac{1}{k} - 2\sum_{k=1}^{U} \frac{1}{2k}$$

$$ = \sum_{k=U+1}^{T} \frac{1}{k}$$

Now $T + U + 1 = p$ so this sum becomes

$$ \frac{1}{T} + \frac{1}{U+1} + \frac{1}{T-1} + \frac{1}{U+2} + \dots $$

(by coming terms from the ends)

$$ = \frac{p}{T(U+1)} + \frac{p}{(T-1)(U+2)} + \dots $$

which is divisible by $p$.