#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. 23, 2020, 8:00pm


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 6

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

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

# Answer 1: Herbert S. Wilf was born on June 13, 1931 in Philadelphia, PA. I've read over the paper. 

# Question 2: Let m:=Age of Donald Trump. 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. 

# Answer 2:
# m:=74, n:= 77. 
# NuGPaths(77,74) = 9212324866083276752554588862297816271201000

# Question 3: What is a Wilf-Zeilberger pair?

# Answer 3: It is a pair of functions that can be used to certify combinatorial identities. 

# Question 4: What nationality was Catalan? What is the constant named after him? 

# Answer 4: Catalan was a French and Belgian mathematician. The constant named after him is the
# the summation from n = 0 to infinity of (-1)^n/(2n+1)^2 = 1/1^2 - 1/3^2 + 1/5^2 - 1/7^2 + .... 
# The numerical value comes out to approximately 0.915965594..... The decimal expansion of Catalan's constant is A006752
# in the OEIS. 

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

# Answer 5: 
# Cycles of [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]}
# Overall: {[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]}
# Paths(3,2): {[-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]}

# Paths(3,2) is equal the set of 10 lists I get. 

# 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,a3...,ak such that the 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 going it in general.
# Extra Credit: Write a Maple Function that does it.

# Answer 6: 

# We will prove this by induction. Our basic step is k=1, which means there is only one can. We are given the condition that the total
# sum of the gas in the gas containers is exactly what is needed to drive in the track. Thus, with just 1 can, we can go the entire track. 
# Our trivial case is true.  Our inductive hypothesis is for some n=1...k, it is possible to find an initial location so that we can
# go around the entire circular track. Now, we will make our inductive step. We will prove that for k+1 that we can go around an entire circuit of the track.
# For this to be true, from the start, we need to be able to find some can c where the amount of gas is greater than the distance to the next
# can. Otherwise, we will certainly not be able to complete an entire circuit. 

# From here, if we poured the contents of can c into the can before it, we'd be at the state of k, which based on the inductive hypothesis
# is true. We know for state k that it is possible to find a starting position x so that we can traverse the entire track. This position x 
# would also make up the initial condition for k+1 cans because the additional can from k just contains part of the previous can. We also
# already know that can c has enough gas to reach the next can, so the can before c needs enough to reach c. This is true because from our
# inductive hypothesis, we know that we already had enough gas to complete the entire circuit with k cans. 

# For the general method, we should first note about the initial can is that the distance between this can and the next can is shorter
# than the amount of gas that can be provided for. Otherwise, you cannot make it past even to the next station. Another thing to note
# is that we are already guaranteed to be able to go around the entire track since we are provided enough gas given that we choose
# the right initial can.

# The algorithm is to keep track of how much gas is in our current tank as we traverse from i=1 to i=k. If the current tank ever goes below 0,
# then we know that we should pick the next station as the starting one as a candidate. With any prior starting station,
# we will not be able to go around fully. Then, we will reset our current tank to 0 as we've chosen a new station as the candidate. 
# The last value we indicated as the starting one will work as the starting one.