\documentclass[11pt]{article} \usepackage{fullpage} \usepackage{url} \usepackage{amsmath} % This is a file of macros and definitions that may come up in % ANY LATEX paper. Typically I'll use this file and some other file in the % directory of the paper, this one for general math things, that one for % things specific to that paper. % % font's used and general paper things. \font\tenrm=cmr10 \font\ninerm=cmr9 \font\eightrm=cmr8 \font\sevenrm=cmr7 % \font\title=cmbx10 scaled \magstep1 % extra big title font \font\ss=cmss10 % used by \proof \font\smallcaps=cmcsc10 % used to label Theorems, etc. % imhibit black bars on overflows % \overfullrule=0pt % % today's date % % % English words that I always italizice in papers. % Some words that appear in math mode alot that I wasn roman % \newcommand{\AREA}{{\rm AREA}} \newcommand{\ALG}{{\rm ALG}} \newcommand{\ACK}{{\rm ACK}} \newcommand{\VC}{{\rm VC}} \newcommand{\AC}{{\rm AC}} \newcommand{\ZL}{{\rm ZL}} \newcommand{\WOP}{{\rm WOP}} \newcommand{\tree}{{\rm tree}} \newcommand{\SUBSEQ}{{\rm SUBSEQ}} \newcommand{\minor}{{\preceq_m}} \newcommand{\minorp}{{\preceq_m'}} \newcommand{\cminor}{{\preceq_{\rm c\hbox{-}m}}} \newcommand{\GM}{{\rm GM}} \newcommand{\TREE}{{\rm TREE}} \newcommand{\R}{\rm R} \newcommand{\B}{\rm B} \newcommand{\G}{\rm G} \newcommand{\Y}{\rm P} \newcommand{\IO}{\exists^\infty} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\into}{{\rightarrow}} \newcommand{\D}{{\sf D}} \newcommand{\N}{{\sf N}} \newcommand{\Z}{{\sf Z}} \newcommand{\Q}{{\sf Q}} \newcommand{\reals}{{\sf R}} \newcommand{\qd}{{\rm qd}} \newcommand{\GE}[1]{{\equiv^{G}_{#1}}} \newcommand{\TE}[1]{{\equiv^{T}_{#1}}} \newcommand{\TES}[1]{{\equiv^{T}_{#1,{\rm S}}}} \newcommand{\TEB}[1]{{\equiv^{T}_{#1,{\rm BOOL(S)}}}} \newcommand{\LL}{{\cal{L}}} \newcommand{\onepe}{1+\epsilon} \newcommand{\oneme}{1-\epsilon} \newcommand{\cool}{cool} \newcommand{\nze}{numzeros} \newcommand{\non}{numones} \newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})} \newcommand{\LH}[2]{ {\rm LH}({#1};{#2})} \newcommand{\bbb}{{\gamma}} \newcommand{\COL}{{\rm COL}} \newcommand{\card}[1]{\#(#1)} \newcommand{\st}{\mathrel{:}} \newcommand{\fhat}{{\hat{f}}} \newcommand{\Ahat}{{\hat{A}}} \begin{document} \centerline{\bf Homework 12, Morally Due 12:30PM, Tue May 5 2026} \newif{\ifshowsoln} %\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \begin{enumerate} \item (0 points) What is your name? \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (30 points) \begin{enumerate} \item (0 points) Write a program that, on input $(n,k,c)$, looks at ALL $c$-colorings of $[n]$, counts how many HAVE a $k$-AP, and divides that by $c^n$. Hence you get the fraction of $c$-colorings that have a mono $k$-AP to 3 places. \item (15 points) For $3\le n\le 7$ determine what fraction of 2-colorings of $[n]$ have a mono 3-AP. Output a table like the one below. THE NUMBERS WE GIVE ARE FALSE or true by accident. \begin{tabular}{|c|l|} \hline $n$ & Fraction of 2-colorings of $[n]$ that have a mono 3-AP \cr \hline 3 & 0.5 \cr 4 & 0.617 \cr 5 & 0.689 \cr 6 & 0.75 \cr 7 & 0.81 \cr 8 & 0.999 \cr \hline \end{tabular} \bigskip \item (15 points) For $3\le n\le 20$ determine what fraction of 2-colorings of $[n]$ have a mono 4-AP. Output a table similar to the one in the last problem. \bigskip \item (0 points) Are the numbers surprising (e.g., more or less than you would have thought)? \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (40 points. This problem is also on the optional project so if you are doing the optional project, then use your answer for both this HW and the project. DO NOT say on the optional project {\it see my answer on HW12}). Let $VDW(k,\omega)$ mean that VDW theorem is known for $k$-APs and ANY number of colors. \bigskip Assume you know VDW theorem for $VDW(1,\omega)$, $VDW(2,\omega)$, $VDW(3,\omega)$, and $VDW(4,\omega)$. Prove VDW theorem for $VDW(5,2)$. \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (30 points. \bigskip You cannot Use Rado's Theorem for this problem. We will be asking you to prove Rado's Theorem in this particular case. You CAN use the Extended VDW theorem. Consider the equation $$E: \\ v+ 2w - 3x + y + 10z =0.$$ Show that there exist a number $M$ such that, for all $\COL\colon [M]\into [2]$, there exists a mono solution to $E$ (The $v,w,x,y,z$ might not be distinct.) \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (0 points. AND YOU MUST DO THIS BY MONDAY SO THAT I CAN TALK ABOUT IT TUESDAY.) What is funniest thing you saw in class. Here are options though you are not limited to them. \begin{enumerate} \item The Bolzano Weisterauss Rap \item The repeated sketch where Ryan's Friend and I changed shirts. \item The Banach Tarski Paradox used to explain the miracle of loaves and fishes. \item The Combinatorics Song \item Bill's Rap about the Infinite Hat Game. \item BAD SEQUENCES! Song about the infinite hat game. \item Bill sold the rights to the song to Who? \item Celebrating Ryan's friend getting his Masters \item {\it That is what Erdos calls it The Happy Ending Theorem. Their marriage lasted 68 years and they died on the same day. We prove this 3 ways.} \item The Application of Ramsey Theory to History. \item Quantum Supremacy vs you-know-what. \end{enumerate} I am sure there are others. For example, \begin{enumerate} \item In the past one of the students said that the poly VDW theorem was funny since the bounds were so big. I didn't do TREE(3) that year which she would have thought was hilarious. \item Some students have pointed to a line or part of a sketch. \end{enumerate} \end{enumerate} \end{document}