\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}$. \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$. NOW we have that all of the $(V-1)$-shares are in $(\gamma,1-\alpha_2)=(\frac{1}{2},1-\alpha_2)$. Is that a contradiction? ONLY IF THE NUMBER OF $(V-1)$-SHARES IS OVER HALF OF ALL SHARES. If $(V-1)S_{V-1} \ge m+1$ then $\alpha_2$ stays $\alpha_2$ and is an upper bound for $f(m,s)$. If $(V-1)S_{V-1} \le m$ 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. \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