wu :: forums « wu :: forums - The non-negative integers » Welcome, Guest. Please Login or Register. Dec 2nd, 2021, 4:12am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, Grimbal, SMQ, Eigenray, william wu, towr, ThudnBlunder)    The non-negative integers « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: The non-negative integers  (Read 4565 times)
wdcefv
Newbie

Posts: 1
 The non-negative integers   « on: Jun 13th, 2014, 4:58am » Quote Modify

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.
 IP Logged
JohanC
Senior Riddler

Posts: 460
 Re: The non-negative integers   « Reply #1 on: Jul 28th, 2014, 3:10pm » Quote Modify

Very interesting.
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.
 IP Logged
dudiobugtron
Uberpuzzler

Posts: 735
 Re: The non-negative integers   « Reply #2 on: Jul 28th, 2014, 6:24pm » Quote Modify

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 Set C 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 in Set A or B 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 Set A and B are negligible in size compared to C?
 « Last Edit: Jul 28th, 2014, 6:25pm by dudiobugtron » IP Logged
gotit
Uberpuzzler

Gender:
Posts: 804
 Re: The non-negative integers   « Reply #3 on: Jul 29th, 2014, 2:20am » Quote Modify

Here is my quick calculation

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

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

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

n(C) = 10N - 10N-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).
 IP Logged

All signatures are false.
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: The non-negative integers   « Reply #4 on: Jul 29th, 2014, 7:28am » Quote Modify

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.

 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »