\documentclass[12pt,HW250,ifthen]{article} \usepackage{comment} \newcommand{\NOBET}{{\rm NOBET}} \newcommand{\ONEFOUR}{{\rm ONEFOUR}} \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{\st}{\mathrel{:}} \usepackage{amsmath} \begin{document} \centerline{\bf Homework 07, Morally due Mon Apr 5, 9:00AM} For Programming Problems: Send your code to Emily by email. Send the actual .java/.py/ect file. You need to use your .umd email address or it will not send. In your pdf, you must have the output your code provides. You can screenshot this or type it in. Hint: Use Python. \begin{enumerate} \item (0 points but if you miss the second midterm that means you got this wrong retroactively and you will lose a lot of points). When is the SECOND midterm? By what day do you need to tell Dr. Gasarch that you cannot make the midterm (if you cannot and know ahead of time)? HINT: The date of the second midterm has been CHANGED. It is now Thursday April 8, 2021. (We did this so that we could have a HW due and gone over BEFORE it.) \centerline{\bf GOTO NEXT PAGE} \newpage \item (30 points) In the country of Fredonia they use two kinds of coins: 6-cent and 7-cent. \begin{enumerate} \item (10 points) Find the number $n_0$ such that \begin{itemize} \item $(\forall n\ge n_0)(\exists n_1,n_2\in\N)[n=6n_1+7n_2]$, and \item $\neg (\exists n_1,n_2)[n_0-1= 6a+7b]$. \end{itemize} \item (20 points) Prove both parts. \end{enumerate} {\bf HINT} Get some empirical evidence, either by hand or by program. You do not have to send Emily your program if you made one. \centerline{\bf GOTO NEXT PAGE} \newpage \item (30 points) Let $P$ be some statement about INTEGERS. Dr. Gasarch proved $P(-8)$. Dr. Gasarch then proved $(\forall n\in\Z)[P(n)\into P(n+3)]$. Fill in XXX in the following sentence $P(n)$ holds iff $n$ satisfies XXX. \centerline{\bf GOTO NEXT PAGE} \newpage \item (40 points) Let $a_n$ be defined as follows $a_0=17$ $(\forall n\ge 1)[a_n = a_{\floor{n/2}} + \floor{\sqrt{n}}]$ \begin{enumerate} \item Write a program that computes $a_n$ and graph it. \item Use your graph to GUESS a number $A,B\in\N$ such that $a_n\le A\sqrt{n} + B$. \item Use constructive induction to DERIVE $A,B$ such that $a_n\le A\sqrt{n} + B$. (You allowed to {\it cheat} and always assume $n/2$ and $\sqrt{n}$ are natural numbers, go avoid dealing with floors.) (This does not have to agree with the answer you got in the last part.) \end{enumerate} \end{enumerate} \end{document}