Purdues math problem of the week

PROBLEM OF THE WEEK  http://www.math.purdue.edu/pow/
Problem No. 14 (Fall 2009 Series)
A set F is called countable if either F is finite or there is a one-to-one
correspondence between the elements of F and the natural numbers.
Two sets A and B are called almost-disjoint if A intersection B is finite.

Prove or disprove: There are uncountably many pairwise almost-disjoint
sets of natural numbers (positive integers). In more formal language:
Does there exist an uncountable set F such that each element of F is a
set of natural numbers and each two elements of F are almost-disjoint?

I think 1+2x+5x+y=10  solve for x and y sounds more enjoyable for the average Gaussian mathematician

This is a hard problem

My problem?? really,I doubt it!

not yours

oops, I knew it! :) I got a bit over exicted there LOL .I doubt most people would get your problem, unless they actually study.

maybe next time I will find a problem thats not so hardcore :D

I like the problem, and it appears non-trivial.

Here's an invalid proof. Rather than delete it, I leave finding the flaw in it as an alternate problem.

========================================================================

Let N be the natural numbers. Let M be a set of almost disjoint subsets of N.

Firstly note that if a set of subsets of N are disjoint the set is countable [each subset (except possibly one) must contain a distinct natural number]. Secondly, for any particular finite set F, the same applies to a set of subsets of N whose pairwise intersection is F [the complement of F in N is countable, and each set (except possibly one) has a distinct member of this complement]. (lemma 1)

Thirdly, there are only countably many finite subsets of the natural numbers. (lemma 2)

Consider the set of pairs of sets in MxM whose intersections are F. This set is countable from lemma 1. The union of such sets of pairs over all finite sets F is countable from lemma 2. This union is the whole of MxM, so we have proved that MxM is countable. Therefore M is countable.

the solution is easy to find and is on my orginal post

Try this new one, would be intresting to see how it would be done I have know idea

PROBLEM OF THE WEEK  http://www.math.purdue.edu/pow/

Problem No. 1 (Spring 2010 Series)
If the integers from 1 to 222,222,222 are written down in succession,
how many of them have at least one zero?
Your answer must be justied without the use of computers.

ok, now that's an easy one, but I will leave it to someone else. The first problem seemed much more interesting to me, but I did not think of a simple proof (I have not looked yet).

I can still count them (one by one) without a computer...  

I can see that it can be got by summing all the additional 'zero containing' integers provided by each digit ... so is probably

22,222,222 + 2,222,222 * 9 + 222,222 * 90 + 22,222 * 900 + 2,222 * 9,000 + 222 * 90,000 + 22 * 900,000 + 2 * 9,000,000 = 160,000,000

but as for proving that, I'm at a bit of a loss. There is probably a much more elegant method in any case.

123,456,789 would have been more interesting, if my math is right...

Thats just a basic counting problem...

Just looked back at this problem after a very long time and realised it had something in common with a problem (as yet unsolved) in the Brainstrainers' group. The common theme is the idea of having a large number of the sets overlapping in a way which does no harm. I then thought of defining the numbers as products of primes to distinguish between sets, and arrived at the following solution.

========================================================================

Break the prime numbers into 2 infinite sets alternately, so p_1=2, q_1=3, p_2=5, q_2=7, p_3=11, q_3=13 and so on.

Consider the set of infinite strings of binary digits. This set is uncountable.

Now define a set of natural numbers for each of these strings as follows.

If the i'th digit is 0, all numbers from the i'th have a factor of p_i. If the i'th digit is 1, all numbers from the i'th have a factor of q_i.

Eg) the string 1001... gives the set of numbers {q_1, q_1*p_2, q_1*p_2*p_3, q_1*p_2*p_3*p_4, ...} =  {3, 3*5, 3*5*11, 3*5*11*19, ...}

This way of defining the sets give an uncountable set of infinite subsets of the natural numbers, and it is easy to check that any two of the sets have a finite intersection.

Somewhat simpler solution uses another way of bifurcating the sets. Define a set for each infinite binary string as the set containing exactly the binary numbers which are truncations of the infinite string. eg the set associated with 10110... is {1, 10, 101, 1011, 10110, ...} .

It is trivial to check that this is an uncountable set of infinite sets of integers which are almost disjoint.

Doh.

Think I missed the two week deadline by almost a year [Or by a few thousand miles and a few decades, depending on how you look at it ]. But now that I've looked up the solution, I think this second one of mine is a little more elegant.