Skip to content

Hints Homework 8

October 27, 2011

Problem 3

Proceed as follows:

  • Randomly {2}-color the integers. Let {A} be a {k}-AP. Calculate the probability that {A} is monochromatic.
  • In HW 7, \#3 you computed the number of {k}-APs in {[1,n]}. Use this to show that the probability that a monochromatic {k}-AP exists in {[1,n]} is

    \displaystyle  		\frac{n^2}{(k-1)2^k} (1+ o(1)).

  • Argue that for large enough {k}, {n = 2^{k/2}} will make this less than {1}.

Problem 4

Here is a `template’: We show that {+} is primitive recursive.

Then we argue as follows:

  • We put {f(0,y) = g(y)} with {g = p_1}, the identity. {g} is primitive recursive since {p_1} (projection of a unary function in the first coordinate) is.
  • We put {f(x+1,y) = h(x,y,f(x,y))}, where {h = S \circ p_3}. {h} is primitive recursive since successor {S} and projection {p_3} are, and the primitive recursive functions are closed under substitution (4).
  • By closure under primitive recursion (5), {f} is primitive recursive, and {f} defines {+}.

Advertisements

From → Homework

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: