#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

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

He was born June 13, 1931 in Philadelphia

2) m:=Age of Donald Trump = 74
Let n:=Age of Joe Biden = 77
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?

NuGPaths(77, 74);
          9212324866083276752554588862297816271201000

NuPaths(77, 74);
         179640334888623896674814482814807417288419500

%%/%;
                               2/39

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. Specifically, a Wilf-Zeilberger pair is a pair of discrete functions (F(n, k), G(n, k)) such that
F(n + 1, k) − F(n, k) = G(n, k + 1) − G(n, k).

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

He was French and Belgian. The Catalan's Constant (usually denoted by K,G, or C) is defined by

K=sum_k=0^(infinity)(-1)^k/(2k+1)^2

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)

{[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]}

I only get 5 cyclic shifts; I am not sure how to get 10.

Paths(3,2) is {[-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]}

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 the a1+a2+...+ak gallons are exactly what you need to drive in this track
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

Proof by induction:

Base Case: 
There is just one container which is enough to drive around the track. Starting from this one container you will be able to go around the whole track.

Inductive Step:
Assume that you are able to go around the whole track when there are k containers. We will now show you can go around with k+1 containers.

To make k+1 containers from k containers, you must pick one container and split the gas into two containers. Now, where you can you put this new (k+1)th container?

If you put it right after any of the other k-1 containers (not the two split containers) you will be able to reach this container if you start at that container. So, just start at the container right before where you put this new container and you will pick it up and be able to make up for the missing gas from the kth container when you reach it.

If you put it right after the kth container and before the next one there are two cases.
(1) The newly formed (k+1)th container can be reached by starting from the kth container before running out of gas.
Then, just start from the kth container and there is no problem picking up this newly formed (k+1)th container. Their combined gas will be able to reach the next container, since their sum must be the original amount of gas before it was split.
(2) Starting from the kth container cannot reach the newly formed (k+1)th container before running out of gas.
Start from the (k+1)th container. By the time you loop back around and reach the kth container, you will have extra gas to make up for the gap in reaching the (k+1)th container from the kth container. (Because the gas in the kth container + the gas in the (k+1)th container has to be equal to the original amount of gas). You will be able to reach the next container / the end of the track.

Thus proved by induction.