#ATTENDANCE QUIZ FOR LECTURE 14 of Dr. Z.'s Math454(02) Rutgers University

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p14
#with an attachment called
#p14FirstLast.txt
#(e.g. p14DoronZeilberger.txt)

#Right after finishing watching the lecture but no later than Oct. 24, 2020, 8:00pm


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 6

PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH, BY THE ANSWER

-----------------------------------
Attendance Question 1:
Where and when was Herbert S. Wilf born?
Look up his paper about "random generation of combinatorial objects"
Advances in Mathematics ca. 1980 and at least skim it.

Herbert S. Wilf was born in Philadelphia on June 13, 1931.

-----------------------------------
Attendance Question 2:

Let m:=Age of Donald Trump
Let n:=Age of Joe Biden

What is the probability that if you take a random lattice walk from [0,0] to [n,m] you will always stay in the region x >= y?

m = 74
n = 77

Good walks from [0,0] to [77,74] = 9212324866083276752554588862297816271201000
Total number of walks from [0,0] to [77,74] = 179640334888623896674814482814807417288419500

Probabilty = first / second = 2/39 = 0.05128205128

-----------------------------------
Attendance Question 3:

What is a Wilf-Zeilberger Pair?

A Wilf-Zeilberger pair is a pair of functions that can be used to certify certain combinatorial identities.
Two functions f and g are a WZ pair iff f(n-1,k) - f(n,k) = g(n,k+1) - g(n,k) and 
lim_{M->+infty or -infty} g(n,M) = 0.


-----------------------------------
Attendance Question 4:

What nationality was Catalan? What is the constant named after him?

Catalan was French and Belgian. Catalan's constant is Sum((-1)^n/(2*n+1)^2, n = 0..infty) which is approximately G = 0.915965594177219015054603514932384110774…


-----------------------------------
Attendance Question 5:

Do the same for [1,1,-1,-1,1] and get a set of 10 SUCH LISTS that is the whole of Paths(3,2):

From before, we have the cyclic shifts of [1,-1,1,-1,1] are {[1,-1,1,-1,1],[-1,1,-1,1,1],[1,-1,1,1,-1],[-1,1,1,-1,1],[1,1,-1,1,-1]}

The cyclic shifts of [1,1,-1,-1,1] are {[1,1,-1,-1,1],[1,-1,-1,1,1],[-1,-1,1,1,1],[-1,1,1,1,-1],[1,1,1,-1,-1]}

Together, they form: 
{[1,-1,1,-1,1],[-1,1,-1,1,1],[1,-1,1,1,-1],[-1,1,1,-1,1],[1,1,-1,1,-1],[1,1,-1,-1,1],[1,-1,-1,1,1],[-1,-1,1,1,1],[-1,1,1,1,-1],[1,1,1,-1,-1]}
which is the whole of Paths(3,2).


-----------------------------------
Attendance Question 6:

You are in a circular track in the desert. At random places there are gas containers with random amounts of gas a1,a2,...,ak such that a1+a2+...+ak gallons are exactly what you need to drive in this track.
[[0,0.1], [0.2,0.5], [0.7,0.4]]
Prove that there exists a location on the circular track such that if you start there you don't run out of gas.
Devise a method for doing it.
Extra credit: Write a Maple function.


Suppose we have a list of places p1,...,pk where there are gas containers with random amounts of gas a1,...,ak such that a1+...+ak gallons are exactly what you need to drive in this track.
Let c1,...,ck be defined as the cost of gas to get from one gas station to the next ie ci = p{i+1%k} - pi.  

To find the location to start, we calculate d1,...,dk where di = Sum(aj - cj, j = 1..i-1) and di basically represents the current amount of gas upon reaching pi (whether it be positive or negative). Then, we pick the index where di is the lowest. That index represents the place to start so that you don't run out of gas. To see this, note that if you calculate d1,...,dk again but starting at a different index (denote these new values as d'1,...,d'k), d'1 - d1 = ... = d'k - dk = a constant. So, if we start at the position i where the original di is the least (ie setting d'1 = di and cyclically matching each of the corresponding variables), then d'1 <= d'i for all 1 < i <= k. Since we know that a1+...+ak = c1+...+ck, we know that d'{k+1} = 0 which would occur at the same place as d'1. So, 0 <= di for all 1 <= i <= k meaning that the amount of gas the car has will always be 0 or positive meaning the car will never run out of gas.