#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 Q. #1 for LECTURE 14
#Where/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.

#ANSWER to Q. #1:	

# Philadelphia, PA on June 13, 1931




#ATTENDANCE Q. #2 for LECTURE 14
#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] ([77,74]) you will always stay in the region x>=y?

#ANSWER to Q. #2:

#about 5.13% (wrote procedure NuPaths2 that doesn't count the path if x<y, then divided by
#NuPaths(77,74) since every path is equally likely in the sample space (random walks)




#ATTENDANCE Q. #2 part 2 for LECTURE 14
#if you toss a fair coin 2000 times what is the probability you get exactly 1000 heads (1000 tails)

#ANSWER to Q. #2 part 2:

#every outcome in the sample space has an equal probability, and since we have n=2000 tosses, there are 2^n = 2^2000 outcomes, getting exactly 1000 heads is binomial(2000,1000), so the probability of this outcome is binomial(2000,1000)/2^2000, or roughly 0.018




#ATTENDANCE Q. #3 for LECTURE 14
#What is a Wilf-Zeilberger pair?

#ANSWER to Q. #3:

#according to Wikipedia, two functions F and G form a Wilf-Zeilberger pair iff:
#1) F(n+1,k)-F(n,k) = G(n,k+1) - G(n,k)
#2) lim as M --> +/- infinity, G(n,M) = 0
# Then, they satisfy the relation G(n,k) = R(n,k)F(n,k-1), where R(n,k) is a rational func of n and k, called
# the "WZ proof certificate"




#ATTENDANCE Q. #4 for LECTURE 14
#What nationality was Catalan? What is the constant named after him?

#ANSWER to Q. #4:

#He was French and Belgian.  His constant called Catalan's constant G, is G= Beta(2) = sum(n=0..inf) of (-1)^n / (2n+1)^2,
#where Beta is the Dirichlet beta function




#ATTENDANCE Q. #5 for LECTURE 14
#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)

#ANSWER to Q. #5: 

#[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]}
#total set:= {[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]}



#ATTENDANCE Q. #6 for LECTURE 14
#you're 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 total amount of 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 track such that if you start there you
#you don't run out of gas
#Devise a method for doing it: Extra credit

#ANSWER to Q. #6:

#Using induction:

#Base case, k = 1: There is only 1 container, but it must have enough gas to go around the track since the sum is only a1
#	So, a starting location is at this first and only container, the base case is proven

#Inductive step: show that situation at k --> situation at k+1 containers

#Assume situation is true at k containers, meaning that there exists a starting point that lets us go around the track
#For any k+1 containers, since the sum a1+a2+...+ak+a_(k+1) is exactly the total amount of gas, there must be one
#instance where a can at position X has enough gas to reach the can at position X+1.  If this wasn't the case then
#there would be no way to close the gap between any two cans, which means that it would be impossible to traverse
#the entire circular track

#Let's take a container (as position Y) that has enough gas to get to the next (@ pos Y+1).  If we ignore the Y+1
# container as its own entity, and rather combine the gas between them into a single container Z (At position where
# Y is), then we are back to k containers, which we know has a solution based on the hypothesis of the inductive step.
# This should work because since we know for sure that we can close the gap between those two, we don't have to worry
# about running out of gas on the path from Y to Y+1, therefore if we make that 1 container with the sum of their
# gallons, we can go back to our k containers, which I think should be enough for the inductive step.

#Since track(k) --> track(k+1) and the base case k=1 is true, a solution should exist for all k >= 1

###

# A method could be to start at each position and keep a sum of gas.  Then, you add the gas you have gotten from this
# station, and check if sum < position(next) - position(current).  If so, continue onward, otherwise, keep going for
# the next position and all the way around the circle, and if we're back at the start of this inner loop, then add
# this position to a set of solutions.  This is costly, however, as it has the potential to run in quadratic time
# in the worst case.  I am unsure how to implement circular structures (liked circular linked lists) in Maple, or if
# there is some much more efficient way to go about this altogether