% LaTex2e \documentclass[12pt]{article} \usepackage{amssymb,latexsym} \usepackage{anysize} %\marginsize{left}{right}{top}{bottom} %\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers \marginsize{2cm}{2cm}{1cm}{3cm} \def\reals{{\mathbb R}} \def\integers{{\mathbb Z}} \def\naturals{{\mathbb N}} \pagestyle{myheadings} \def\header{{\hfill Final Exam \hfill A. Miller \hfill Spring 2005 \hfill Math 240\hfill}} \markboth\header\header \newcount\probno \newcount\total \newwrite\examTBLFile \probno=0 \def\prob#1{\advance\probno by 1 \par \vfill \newpage \noindent\the\probno . (#1 pts)\advance\total by #1 \immediate\write\examTBLFile{\the\probno \string& #1 \string& \string\qquad \string\\ \string\hline}} \def\finishtbl{ \immediate\write\examTBLFile{Total \string& \the\total \string& \qquad \string\\ \string\hline} } \newwrite\ans \immediate\openout\ans=answers \outer\def\answer{\par\medbreak \immediate\write\ans{} \immediate\write\ans{\string\bigskip \the\probno . } \copytoblankline} \outer\def\answerx{\par\medbreak \immediate\write\ans{} \immediate\write\ans{\string\bigskip \the\probno . } \copytoblankline} \outer\def\putanswer{\par\medbreak \immediate\write\ans{} \copytoblankline} \def\copytoblankline{\begingroup\setupcopy\copyans} \def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials \catcode`\|=12\obeylines} {\obeylines \gdef\copyans#1 {\def\next{#1}% \ifx\next\empty\let\next=\endgroup% \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}} \def\printanswers{\newpage\begin{center} Answers \end{center} \immediate\closeout\ans\input answers} % \def\answer{\par\bigskip\bigskip\bigskip\noindent Answer: \par} % \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak \begin{document} \bigskip Show all work. % Simplify your answers. % Circle your answer. \bigskip No books, no calculators, no cell phones, no pagers, no electronic devices of any kind. However you can bring to the exam one $8.5$ by $11$ cheat sheet with anything you want written or printed on both sides. \par\vskip .25in \begin{center} Name\makebox[3in]{\hrulefill} \\ \end{center} \bigskip Circle your Discussion Section: \begin{verbatim} DIS 303 12:05p T B235 VAN VLECK DIS 304 12:05p R B235 VAN VLECK DIS 307 2:25p T B139 VAN VLECK DIS 308 2:25p R B309 VAN VLECK \end{verbatim} \bigskip \begin{center} \Large \begin{tabular}{||c|c|c||} \hline\hline Problem & Points & Score \\ \hline\hline \input{exam.tbl} \hline \hline \end{tabular} \end{center} \immediate\openout\examTBLFile=exam.tbl \bigskip Solutions will be posted shortly after the exam: www.math.wisc.edu/$\sim$miller/m240 \setcounter{page}{0} \newpage \prob{10} % 2.3-17 (did problem 1.8-17 instead) Give examples of functions from the set of integers, $$\integers=\{0,1,-1,2,-2,3,-3,\ldots\},$$ to the set of natural numbers, $$\naturals=\{1,2,3,\ldots\},$$ having the given properties. \bigskip (a) $f:\integers\to \naturals$ such that $f$ is one-to-one and onto. \def\myskip{\vskip 1.8in} \myskip (b) $g:\integers\to \naturals$ such that $g$ is onto, but not one-to-one. \myskip (c) $h:\integers\to \naturals$ such that $h$ is one-to-one, but not onto. \myskip (d) $k:\integers\to \naturals$ such that $k$ is neither one-to-one nor onto. \prob{10} % 2.5- 3 Convert the integer $1 1111 0101$ from binary notation (base 2) to: \bigskip (a) hexadecimal notation (base 16) \myskip (b) octal notation (base 8) \myskip (c) decimal notation (base 10) \prob{10} % 2.7-31 In this problem matrix operations are done using the bit operations $\vee$ and $\wedge$ instead of $+$ and $\cdot$. $$A=\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array}\right]$$ \bigskip (a) Find $A^{[2]}$ \def\myskip{\vskip 2in} \myskip (b) $A^{[3]}$ \myskip (c) $A\vee A^{[2]}\vee A^{[3]}$ \prob{10} % 3.1-41 Given an integer $a_n$ if $a_n$ is even let $a_{n+1}=a_n/2$, if $a_n$ is odd let $a_{n+1}=3a_n+1$. The $3x+1$ conjecture states that given any positive integer $a_0$ there exists an integer $n\geq 0$ such that $a_n=1$. Prove that this conjecture is true for $a_0=17$. \prob{10} % 3.2-33 If $A$ is an uncountable set and $B$ is a countable set, must $A\setminus B$ be uncountable? Prove it. \prob{10} % 3.4-41 For $w$ a string of symbols and $i$ a positive integer let $w^i$ represent the concatenation of $i$ copies of $w$. Prove using mathematical induction that $len(w^i)=i\cdot len(w)$ where $len(w)$ stands for the length of $w$. \answer Base: $len(w^1)=len(w)=1\cdot len(w)$ \par Inductive step: Assume $len(w^i)=i\cdot len(w)$. Then \par $len(w^{i+1})=len(w^{i}w)=len(w^i)+len(w)=i\cdot len(w)+len(w) =(i+1)\cdot len(w)$ \prob{10} % 4.3-15 In how many ways can a set of four letters be selected from the English alphabet assuming the following: \def\myskip{\vskip 1.2in} \bigskip (a) They are distinct and the order in which you select them counts. \myskip (b) They are distinct but the order in which you select them does not count. \myskip (c) They may not be distinct but the order in which you select them counts. \myskip (d) They may not be distinct and the order in which you select them does not count. \answer (a) $26\cdot 25\cdot 24\cdot 23$ (b) $C(26,4)$ (c) $26^4$ (d) $C(29,4)$ \prob{10} % 7.3-27 too much work to draw graph - so I reversed it Draw a digraph which represents the binary relation: $$R=\{(a,a),(b,b),(d,d),(a,b),(b,c), (c,a),(a,c)\}$$ \prob{10} % 7.5-11 (a) Let the relation $R$ on the set $D$ of all differentiable functions from $\reals$ to $\reals$ consist of all pairs $(f,g)$ such that $f^\prime(x)=g^\prime(x)$ for all real numbers $x$. Prove that $(D,R)$ is an equivalence relation. \vskip 5in \par (b) Which functions are in the same equivalence class as the function $$f(x)={x^3\over 3}$$ \answer (b) $\{{x^3\over 3}+C\;\; :\;\; C\in\reals\}$ \prob{10} % 9.1- 5 - did 11 instead - too hard to draw pictures. How many rooted trees are there with the three vertices $\{a,b,c\}$? Draw them. \answer 9 \finishtbl \newpage The following program was used to pick the problems on the test. I changed a few and dropped two. For example, instead of 2.3-17 I used problem 1.8-17. \begin{verbatim} #! /usr/ucb/python import string import sys import random random.seed("Harpo, Groucho, and Chico") f=open("hmwk1",'r') # input file lines=f.readlines() lines=lines[19:] problems=[] for line in lines: s=string.split(line) if len(s)>0: section=s.pop(0) prob=random.choice(s) problems.append(section+"-"+prob.rjust(2)) f=open("hmwk2",'r') # input file lines=f.readlines() lines=lines[32:] for line in lines: s=string.split(line) if len(s)>0: section=s.pop(0) prob=random.choice(s) problems.append(section+"-"+prob.rjust(2)) random.shuffle(problems) test=problems[0:8] f=open("hmwk3",'r') # input file lines=f.readlines() lines=lines[28:] problems=[] for line in lines: s=string.split(line) if len(s)>0: section=s.pop(0) prob=random.choice(s) problems.append(section+"-"+prob.rjust(2)) random.shuffle(problems) problems=problems[0:4] for prob in problems: test.append(prob) test.sort() for prob in test: print prob OUTPUT: 2.3-17 2.5- 3 2.7-31 3.1-41 3.2-33 3.4-41 3.6- 5 4.3-15 7.3-27 7.5-11 7.6-53 9.1- 5 \end{verbatim} \printanswers \end{document}