#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

QUESTION #1:

Where and when was Herbert S. Wilf born?

ANSWER:

He was born on June 13, 1931 in Philadelphia, Pennsylvania.


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:

We have m = 74, n = 77.

The probability is given by the number of good paths from [0,0] to [77,74] to the total number of paths from [0,0] to [77,74].

The number of walks where it always stays in x>=y is given by
NuGPaths(77, 74): 9212324866083276752554588862297816271201000

The total number of walks is given by:
NuPaths(77, 74): 179640334888623896674814482814807417288419500

So, the probability is 0.05128205128.


QUESTION #3:

What is Wilf-Zeilberger pair?

ANSWER:

According to Wikipedia, it is a pair of functions that can be used to certify certain combinatorial idenities. They are used in the evaluation of many sums involving binomial coefficients, factorials, and in general any hypergeometric series.

QUESTION #4:

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

ANSWER:

He was French and Belgian.

The constant is:
G = sum((-1)^n / (2n+1)^2, n=0..infinity))

QUESTION #5:

Find the set of cycle shift for [1,1,-1,-1,1] and get a set of 10 such lists that is the whole of Paths(3,2).

ANSWER:

Set of Cycle Shifts:

{[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 set of 10 lists making up Paths(3,2) is given by:

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


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 the sum 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.

ANSWER: 

First take any point i from 1 to k on the circle. Continue around the circle until you reach a point, call it j, where you do not have enough fuel to travel from location j to j+1. If there is no such point, then i is our desired point. So assume that there exists such a point j. Now repeat this process by starting at point j+1 and traveling around the circle until you reach a point, call it m, such that you do not have enough fuel to go from m to m+1. Eventually, since you are traveling in a circle you will once again reach location i. Let n be the last point such that there was not enough fuel in the tank to travel from n-1 to n. We claim that n is the desired point to start at which will allow you to not run out of gas. When we traveled from i to n-1 we accumulated sum(a_i, i to n-1) amount of gas which is less than the distance from location i to location n-1, because of all the points we noted where we did not have enough fuel to keep traveling. Since our assumption is that a1 + a2 + ... + ak gallons are exactly what you need to travel through the circle, then it must be true that the amount of fuel from n to i-1 is not only enough to get from n to i-1, but it must also compensate for all the extra fuel needed to travel from i to n-1. Hence, if we start at location n then we will gather the extra fuel needed to travel from i to n-1 while traveling from n to i. So, n is our desired point.

Program:

Algorithm:

Loop through every point and see if starting there will allow you to make it through the track.

# (a) is a list of amount of fuel at locations
cycleP:=proc(a) local k,i,s,d,j,index:

k:=nops(a):
# d is distance traveled
d:=0:
# s is sum of fuel accumulated
s:=0:

for i from 1 to k do
	s:=0:
	d:=0:
	for j from 1 to k do
		index:=(i+j-1) mod k:
		s:=s+a[index]:
		d:=d+1:
		if s < d+1 then
			# can't start at this i because you will not have enough fuel 
			break
		fi:
	od:
	RETURN(i):
od:

RETURN('FAIL'):

end: