\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}
\begin{document}
\centerline{\bf Final-Untimed MORALLY Due May 11 at 9:00AM}
\newcommand{\Prob}{{\rm Pr}}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}
\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}
\centerline{\bf MANY OF THE PROBLEMS ARE WORTH 0 POINTS}
\centerline{\bf THEY ARE TO WRITE SHORT PROGRAMS}
\centerline{\bf THERE WILL BE A PROBLEM WORTH REAL POINTS THAT USES THEM}
\begin{enumerate}
\item
(0 points but please DO IT)
What is your name?
What day is the timed final?
\item
(0 points BUT YOU REALLY NEED TO DO THIS TO UNDERSTAND AND TO THE
NEXT TWO PROBLEMS ON THIS HW)
Read and understand the notes on THE HALF METHOD on the course
websites of class slides.
\item
(0 points)
For all programs in this problem I specify the output. You may need to modify
that part when you use a program as a subroutine in another program.
In this problem and the next we will guide you through the writing of several short programs
which you will later put together.
The final goals are:
\begin{itemize}
\item
A program that will, given $(m,s,\alpha)$ determine if $f(m,s)\le \alpha$.
It will try both the Floor-ceiling method (henceforth FC) and the HALF method.
It may return that NEITHER method worked.
\item
A program that will, given $(m,s)$ determine the smallest $\alpha$ for which
$f(m,s)\le \alpha$ can be proven by either FC or HALF.
(This will be done in the next problem though it will draw on this problem.)
\end{itemize}
\begin{enumerate}
\item
{\it CHECK-Program.} Input is $(m,s,\alpha)$. Check that $m>s$ and $\alpha>\frac{1}{3}$.
If either is false then output {\it BAD INPUT.} If not then output {\it GOOD INPUT.}
When writing the programs below separately they should all begin with CHECK.
When you put them together into a big program, the big program should begin with CHECK.
\item
{\it FC-Program.} Input $(m,s,\alpha)$.
If $f(m,s)\le \alpha$ follows from FC then output {\it FC establishes bound.}
If not then output {\it FC does not establish bound.}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
{\it $V$-Program.} Input $(m,s,\alpha)$.
We begin doing the HALF method.
We need to know $V\in\N$ such that
\begin{itemize}
\item
NOBODY has $\ge V+1$ pieces.
If someone has $\ge V+1$ pieces than some piece is $\le \frac{m}{s}\frac{1}{V+1}$.
Hence we need
$\frac{m}{s}\frac{1}{V+1} \le \alpha.$
\item
NOBODY has $\le V-2$ pieces.
If someone has $\le V-2$ pieces than some piece is $\ge \frac{m}{s}\frac{1}{V-2}$.
That pieces buddy is $\le 1-\frac{m}{s}\frac{1}{V-2}$.
Hence we need
$1-\frac{m}{s}\frac{1}{V-2} \le \alpha.$
\end{itemize}
If there exists such a $V$ then output {\it Use $V$ for HALF.}
If not then output {\it No $V$ exists, so HALF won't work.}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
{\it Equations-Program.} Input is $(m,s,\alpha,V)$ where $V$ is the output
from the $V$-program. Let
\begin{itemize}
\item
$s_{V-1}$ be the number of students who get $V-1$ shares.
\item
$s_{V}$ be the number of students who get $V$ shares.
\end{itemize}
Since there are $2m$ pieces
$$(V-1)s_{V-1} + Vs_V = 2m$$
Since there are $s$ students
$$s_{V-1} + s_V = s$$
Solve this system of 2 equations in two variables to output $s_{V-1}$ and $s_V$.
(Note that this step did not require $\alpha$.)
If $s_{V-1},s_V\in\N$ and are $\ge 1$ then Output $(s_{V-1},s_V)$.
If not then output {\it $(s_{V-1},s_V)$ out of bounds, so HALF won't work.}
{\it Advice} Solve them on paper yourself and then just use those formulas.
\vfill
\centerline{\bf GOTO Next Page}
\newpage
\item
{\it $V$-share-Intervals-Program.} Input is $(m,s,\alpha,V)$ where
$V$ comes from the $V$-program.
We want to find the intervals for the $V$-shares.
The $V$-shares will be in $(\alpha,\beta)$ for some $\beta$ that we want to find.
We derive $\beta$ by contradiction. Assume there is some $V$-share of size $\ge \beta$.
Assume Alice has that share and of course $V-1$ other shares. Call those
shares $p_1\le \cdots\le p_V$. Then
$$\sum_{i=1}^V p_i = \frac{m}{s}$$
$$\sum_{i=1}^{V-1} p_i = \frac{m}{s} - p_v\le \frac{m}{s}-\beta$$
Then
$$p_1 \le \frac{ (m/s)-\beta }{V-1}$$
Recall that we are assuming $p_1>\alpha$. In order to get a contradiction
we will set:
$$\biggl (\frac{ (m/s) - \beta }{V-1} \biggr ) < \alpha$$
$$\frac{m}{s} - \beta< \alpha(V-1)$$
$$\beta > \frac{m}{s}-\alpha(V-1)$$
Hence we take $\beta = \frac{m}{s}-\alpha(V-1)$.
If $\alpha< \beta < 1-\alpha$ then output {\it $\beta$.}
If note then output {\it $\beta$ does not work, HALF method fails.}
\vfill
\centerline{\bf GOTO Next Page}
\newpage
\item
{\it $(V-1)$-share-Intervals-Program.} Input is $(m,s,\alpha,V)$ where
$V$ comes from the $V$-program.
We want to find the intervals for the $V-1$-shares.
The $V$-shares will be in $(\gamma,1-\alpha)$ for some $\gamma$ that we want to find.
We derive $\gamma$ by contradiction. Assume there is some $V-1$-share of size $\le \gamma$.
Assume Alice has that share and of course $V-2$ other shares. Call those
shares $p_1<\cdots\gamma$ then output NOT GOING TO WORK (or something like that).
\item
The $V$-shares are in $(\alpha,\beta)$. Hence there are $Vs_V$ shares in
$(\alpha,\beta)$.
\item
The $(V-1)$-shares are in $(\gamma,1-\alpha)$.
Hence there are $(V-1)s_{V-1}$ shares in
$(\gamma,1-\alpha)$.
\end{itemize}
IF $\beta \le \frac{1}{2} \le \gamma$ AND $Vs_V \ne (V-1)s_{V-1}$ then there are
to many shares on one side of $\frac{1}{2}$ and thats a contradiction.
If that is the case then output {\it HALF method worked!}
IF not then output {\it HALF method did not work.}
\vfill
\centerline{\bf GOTO Next Page}
\newpage
\item
{\it FINAL-FC-VHALF-Program.} Input is $(m,s,\alpha)$.
\begin{itemize}
\item
Run FC-program. If it verifies $f(m,s)\le \alpha$ then output
$f(m,s)\le\alpha$ by the FC theorem.
\item
If not then run all of the programs above up to an including VHALF.
If VHALF verifies $f(m,s)\le \alpha$ then output
{\it $f(m,s)\le\alpha$ by the HALF theorem with parameters $(V,s_{V-1},s_V,\beta,\gamma)$. }
\item
If neither one verifies then output
{\it $f(m,s)\le \alpha$ cannot be proven by FC or HALF.}
\end{itemize}
\end{enumerate}
\vfill
\centerline{\bf GOTO Next Page}
\newpage
\item
The following are true facts:
\begin{itemize}
\item
When the HALF method works then $V=\ceil{\frac{2m}{s}}$.
\item
When the HALF method works either $\beta=\frac{1}{2}$ or $\gamma=\frac{1}{2}$.
\end{itemize}
We use these two facts to DERIVE $\alpha$ FROM $(m,s)$.
\begin{enumerate}
\item
{\it EASY-$V$-Program.} On input $(m,s)$ output $V=\ceil{\frac{2m}{s}}$.
\item
{\it Equations-Program.} On input $(m,s,V)$ output $s_V$ and $s_{V-1}$.
Same as in t Problem 3 since, as we noted, the {\it Equations Program} uses
$(m,s,V)$ but not $\alpha$.
IF the equations do not have a solution where $s_V, s_{V-1}\ge 1$ then
skip the $\beta$ and $\gamma$ steps and set $\alpha_1=\alpha_2=1$.
\item
{\it $\beta=\frac{1}{2}$-Program.} Input $(m,s,V)$
Recall that in the program in Problem 3 we had that the
$V$-shares were in $(\alpha,\beta)$ where
$$\beta = \frac{m}{s}-\alpha(V-1).$$
But this time we are going to {\it assume} $\beta=\frac{1}{2}$.
With that in mind output what $\alpha$ is.
Call it $\alpha_1$ (for now).
NOW we have that all of the $V$-shares are in $(\alpha_1,\beta)=(\alpha_1,\frac{1}{2})$.
Is that a contradiction? ONLY IF THE NUMBER OF $V$-SHARES IS NOT EQUAL TO THE
NUMBER OF $V$-SHARES IN THE OTHER HALF.
If $VS_V \ne (V-1)S_{V-1}$ then $\alpha_1$ stays $\alpha_1$ and is an upper bound for $f(m,s)$.
If $VS_V = (V-1)S_{V-1}$ then $\alpha_1$ is WORTHLESS. Rather than make this a special case,
set $\alpha_1$ to 1 so that later it will NOT be chosen as the upper bound.
(I think this never happens.)
ONE MORE CASE: If $\alpha_1<\frac{1}{3}$ then the HALF method cannot be used
since it depends on every piece being cut into TWO pieces. But this still may
be trying to tell us something. Set $\alpha_1=\frac{1}{3}$.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
{\it $\gamma=\frac{1}{2}$-Program.} Input $(m,s,V)$
Recall that in the program in Problem 3 we had that the
$(V-1)$-shares were in $(\gamma,1-\alpha)$ where
I LEFT $\gamma$ to YOU to figure out.
But this time we are going to {\it assume} $\gamma=\frac{1}{2}$.
With that in mind output what $\alpha$ is.
Call it $\alpha_2$.
If $VS_V \ne (V-1)S_{V-1}$ then $\alpha_2$ stays $\alpha_2$ and is an upper bound for $f(m,s)$.
If $VS_V = (V-1)S_{V-1}$ then $\alpha_2$ is WORTHLESS. Rather than make this a special case,
set $\alpha_2$ to 1 so that later it will NOT be chosen as the upper bound.
(I think this never happens.)
ONE MORE CASE: If $\alpha_2<\frac{1}{3}$ then the HALF method cannot be used
since it depends on every piece being cut into TWO pieces. But this still may
be trying to tell us something. Set $\alpha_2=\frac{1}{3}$.
\item
{\it Find-$\alpha$-Program.} Input $(m,s)$.
\begin{itemize}
\item
Run the programs above to
get $\alpha_1$ and $\alpha_2$.
\item
If $\alpha_1<1$ then run FINAL-FC-VHALF on $(m,s,\alpha_1)$. If it says YES then do nothing.
If it says NO then set $\alpha_1$ to 1.
\item
If $\alpha_2<1$ then run FINAL-FC-VHALF on $(m,s,\alpha_2)$. If it says YES then do nothing.
If it says NO then set $\alpha_2$ to 1.
\item
Compute $\alpha_3=FC(m,s)$.
\item
If $\alpha_3\le \min\{\alpha_1,\alpha_2\}$ then output
\centerline{\bf $f(m,s)\le \alpha_3$ via FC method}
and stop.
\item
(If you got to this step then the FC method was NOT optimal.)
$\alpha \leftarrow \min\{\alpha_1,\alpha_2\}$
Output
\centerline{{\bf $f(m,s)\le \alpha$ via HALF method}}
and stop.
\end{itemize}
\end{enumerate}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(0 points) Write a program that will on input $M,S$ with $M>S$, do the following:
\begin{itemize}
\item[]
For $s=3$ to $S$
\begin{itemize}
\item[]
For $m=s+1$ to $M$
\begin{itemize}
\item[]
If $m,s$ are relatively prime
\begin{itemize}
\item[]
Run Find-$\alpha$-Program on $(m,s)$.
\end{itemize}
\end{itemize}
\end{itemize}
\end{itemize}
The output should be a table like the following
(we do the case of $S=4$ and $M=7$, though the data is not correct).
\[
\begin{array}{|c|c|c|c|}
\hline
m & s & \alpha & \hbox{Method} \cr
\hline
3 & 4 & \frac{5}{12} & FC \cr
3 & 5 & \frac{7}{15} & FC \cr
3 & 7 & \frac{13}{30} & HALF \cr
4 & 5 & \frac{7}{24} & HALF \cr
4 & 7 & \frac{1}{3} & FC \cr
\hline
\end{array}
\]
\item
(20 points) Email the program to Emily AND run it for $M=100$, $S=50$
and give us the table.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(15 points)
Emily might {\it teach} 250H in Spring 2023 (Bill is going on sabbatical).
She will need help designing problems! In this problem you will help her!
Use constructive strong induction to
give TEN 2-tuples $(A,B)$ of RATIONALS with $0