wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The non-negative integers
        
(Message started by: wdcefv on Jun 13^th, 2014, 4:58am)

Title: The non-negative integers
Post by wdcefv on Jun 13^th, 2014, 4:58am

The non-negative integers are divided into three groups as follows:
A= {0,3,6,8,9,...}, B= {1,4,7,11,14,...}, C= {2,5,10,13,...}
Explain.

Title: Re: The non-negative integers
Post by JohanC on Jul 28^th, 2014, 3:10pm

Very interesting.
[hide]Maybe you first tried to straighten some numbers, and then got to round some other numbers. But you were left with a whole bunch that is neither the one nor the other, neither fish nor fowl. [/hide]

Title: Re: The non-negative integers
Post by dudiobugtron on Jul 28^th, 2014, 6:24pm

Awesome riddle wdcefv, and great deduction JohanC. I had thought at length about this puzzle and gotten nowhere; I'd in fact given it up for unsolvable.

If JohanC's solution is the intended one, then it raises some interesting questions about the relative sizes of the sets. Obviously [hide]Set C[/hide] will grow at an increasingly faster rate as you keep adding numbers. It also seems that, for some random n-digit number, the chance that it is [hide]in Set A or B[/hide] decreases as n increases. My question is - what are the relative sizes (measures?) of these sets? I understand all three sets are infinitive, but is there a way to compare them that shows whether [hide]Set A and B are negligible in size compared to C[/hide]?

Title: Re: The non-negative integers
Post by gotit on Jul 29^th, 2014, 2:20am

Here is my quick calculation

For a N-digit non-negative integer, where N > 1

n(A) = 4 * 5^N-1
Reason: A can contain numbers that have only 0,3,6,8 or 9 as its digits

n(B) = 3^N
Reason: B can contain numbers that have only 1,4,7 as its digits

n(C) = 10^N - 10^N-1 - (n(A) + n(B))
Reason: Subtract n(A) + n(B) from the number of possible N-digit integers.

So as N becomes bigger, n(A) and n(B) will become negligible compared to n(C).

Title: Re: The non-negative integers
Post by rmsgrey on Jul 29^th, 2014, 7:28am

It's a known result that practically every number has a 5 among its digits - more formally: for any probability p>0, there exists an N, such that for all n>N, when you select a single number uniformly at random from all positive integers up to n, the probability that there is no 5 among its digits is less than p.

That |A+B| / |C| -> 0 follows trivially from that result.