\documentclass[12pt]{article} \newcommand{\st}{\mathrel{:}} \newcommand{\N}{{\sf N}} \newcommand{\Q}{{\sf Q}} \newcommand{\R}{{\sf R}} \newcommand{\Z}{{\sf Z}} \newcommand{\I}{{\sf I}} \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{\Rpos}{{\sf R}^+} \usepackage{amsmath} \usepackage{comment} \begin{document} \centerline{\bf 250 Untimed Final. Morally Due Mo May 6, 10:00AM} \section{A Variant on Coin Problems} (16 points) The Daleks only have (1) 10-cent coins, and (2) 13-cent coins. Assume Davros and Emily both have an infinite number of 10-cent coins and of 13-cent coins. If Emily wants to give Davros 3 cents SHE CAN: (a) Emily gives Davros a 13-cent coin, (b) Davros gives Emily a 10-cent coin. \begin{enumerate} \item (3 points) Show how Emily can give Davros 1 cent. Mathematically this means you need show $$(\exists x,y\in\Z)[13x+10y=1]$$ (NOTE- this differs from the usual coin problem in that we allow negative coefficients.) {\it Hint:} Nothing fancy here, just use trial and error. \item (10 points) Show BY INDUCTION that $(\forall n \ge 1)(\exists x,y\in \Z)[13x+10y=n].$ \item (3 points) A {\it coin set} is a set of two distinct nonzero natural numbers. A coin set $\{c,d\}$ is {\it evil} if there is some $n$ such that $$(\forall x,y\in\Z)[n \ne cx+dy].$$ Note that $\{10,13\}$ is NOT evil. Does there exists an evil coin set? If YES then give one and prove that it is evil. If NO then prove that there are no evil coin sets. \end{enumerate} \newpage \section{Writing Numbers As Sums of Cubes} (17 points) We consider when a number can be a sum of (how many?) cubes. We consider both allowing the cubes to be integers, and restricting them to naturals. Parts a,b,c,d will show that this distinction matters. \begin{enumerate} \item (1 points) Write 23 as the sum of 9 positive cubes. \item (2 points) Show that 23 cannot be written as the sum of 8 positive cubes. \item (1 points) Write 23 as the sum of 4 integer cubes. \item (2 points) Write a program to determine if 23 can be written as $$x^3+ y^3 + z^3$$ where $-20\le x,y,z \le 20.$ Report either \begin{itemize} \item There exists $x,y,z\in\Z$ such that $$23=x^3+ y^3 + z^3.$$ And the $x,y,z$ are FILL IN IT. \item There is no $x,y,z\in\Z$ with $-20\le x,y,z \le 20$ such that $$23=x^3+ y^3 + z^3.$$ \end{itemize} \textbf{Send Code to Emily (ekaplitz@umd.edu)} \item (2 point) Determine the set $$X = \{ x^3 \pmod {9} \st x\in \{0,\ldots,8\}\}.$$ \item (2 points) Show that if $x\equiv 4 \pmod 9$ then $x$ is NOT the sum of 3 integer cubes. ({\it Hint:} Show that any 3 elements of $X$ from the last Part can never sum to 4 mod 9.) \item (2 points) Show that if $x\equiv 5 \pmod 9$ then $x$ is NOT the sum of 3 integer cubes. ({\it Hint:} Show that any 3 elements of $X$ from the last Part can never sum to 5 mod 9.) \item (0 points but you will need this for the next part) From the last two parts we have the following: If $n\equiv 4,5 \pmod 9$ then $n$ CANNOT be written as the sum of 3 integer cubes. We wonder if the converse is true. The converse is \medskip {\it If $n\equiv 0,1,2,3,6,7,8 \pmod 9$ then $n$ CAN be written as the sum of 3 integer cubes. } \medskip Write a program that will, given a number $N$, determine for $1\le n\le N$, if there exists $x,y,z$ with $-20\le x,y,z\le 20$ such that $$n= x^3 + y^3 + z^3.$$ (The program can use the following shortcut: For each $n$ that you are trying to determine if it is the sum of 3 cubes, first check if $n\equiv 4,5 \pmod 9$. It is it then NO NEED TO LOOK AT $(x,y,z)$'s --- JUST SAY NO!) \textbf{Send Code to Emily (ekaplitz@umd.edu)} To describe the format of the output I give an example. Here is the output if $N=6$. \[ \begin{array}{|c|c|c|} \hline n & \hbox{Y or N?} & x,y,z \cr \hline 1 & Y & 1^3+0^3+0^3 \cr 2 & Y & 1^3+1^3+0^3 \cr 3 & Y & 1^3+1^3+1^3 \cr 4 & N & \cr 5 & N & \cr 6 & Y & 2^3+(-1)^3+(-1)^3 \cr \hline \end{array} \] \item (5 points) Run the program on $N=120$. Output the table. Let $Y$ be the set of numbers $n$ such that (a) $n\not\equiv 4,5 \pmod 9$, and (b) your program DID NOT find $-20\le x,y,z\le 20$ such that $n=x^3+y^3+z^3$. Give us your set $Y$. \end{enumerate} \newpage \section{A New Kind of Poker} (17 points) In this problem the terms {\it straight} and {\it flush} will WILL include a straight flush. We also allow wrap-around, so $Q,K,A,1,2$ is a straight. {\bf Example:} probability of getting a straight in 5-card poker: Number of straights: Pick a card to be the start of the straight. The next four cards ranks are determined so pick their suites. So there are $$13 \times 4 \times 4\times 4 \times 4= 13\times 4^5.$$ Hence the probability of getting a straight is $\frac{13\times 4^5}{\binom{52}{5}}$. \bigskip Assume we are playing poker with a deck that has $s$ suites, $r$ ranks, and each hand has $h$ cards. (We will use letters for suites and numbers for rank.) We will assume $h\le r,s$. We will also assume $h\equiv 0 \pmod 3$. \begin{enumerate} \item (3 points) What is the probability of getting a straight? This will be a function of $h,r,s$. \item (3 points) What is the probability of getting a flush? This will be a function of $h,r,s$. \item (3 points) A {\it Bill-House} is when $2h/3$ of the cards are of one rank, and the other $h/3$ are of another rank. {\bf Example:} If $h=6$, $s=26$ $r=20$ then the following is a Bill-House: $$\{ 1a, 1c, 1e, 1f, 4a, 4b \}.$$ What is the probability of getting a Bill-House? This will be a function of $h,r,s$. \item (0 points but you will need this for the next part) Write a program that will, given $H,S,R$, do the following: \begin{enumerate} \item For all $(h,r,s)$ where $h\equiv 0 \pmod 3$, $3\le h\le H$, $h\le r\le R$, and $h\le s\le S$. computes the probability of getting a straight, a flush, and a bill-house and note how the probs are ordered. Use the built in functions for combinations. The data should be formatted as follows (the numbers are made up). \[ \begin{array}{|c|c|c|c|c|c|c|} \hline h & r & s & \hbox{Prob Flush} & \hbox{Prob Straight} & \hbox{Bill-house} & \hbox{order} \cr \hline 3 & 3 & 3 & 0.3 & 0.4 & 0.2 & BH