Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Questions about coverings and some odd question.

  1. Dec 22, 2006 #1
    1. i need to show that the set A={x in Q|0<=x<=1}
    Q is the rationals set.
    can be covered by open intervals I_k (k is natural number) which the total sum of their lengths is smaller than 1/100.
    2. an integer number is called simple if you can write it by the letters ),(,1,2,+,* (* is multiplication) when we can use the letters at most 10 times.
    i need to show that there exists a natural number N,
    1<=N<=10000000000 which isnt simple.

    for the first question im not sure,
    i need to show that A is a subset of the union of open intervals which their total length is smaller than 1/100, obviously we can dissect A into,
    (0,1/1000),(1/1000,2/1000),....(999/1000,1) but then we don't have the end points included.
    perhaps the end points should be irrational, cause they anyway cannot be attained in the set A?

    for the second question i dont have a clue, i thought perhaps give an ad absurdum proof, suppose every natural number in the interval [1,10000000000] is simple then the number of those numbers is 10000000000, and we have used at most 100000000000,
    if we show that the cardinality of the set of letters used is smaller than the cardinality of the set of simple numbers in this interval than we have a contradiction, but im finding it hard to find a one to one function between sets, i dont know how to even to define one.

    any help?
     
  2. jcsd
  3. Dec 22, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    1. Trying to cover the whole interval [0, 1] cannot possibly work, since it has length one, and thus any collection of intervals that covers [0, 1], or even most of [0, 1], must have total length at least 1. (e.g. the collection you wrote down has total length exactly 1)

    Your intervals are allowed to overlap, by the way.



    2. I think you're overthinking it; it's just a counting problem.
     
  4. Dec 22, 2006 #3
    then how to solve question two?
    i think i solved question 1, bacause every x in A is in the interval (x-e/2^k+2,x+e/2^k+2) so the set A is covered by: U(x-e/2^k+2,x+e/2^k+2)
    where k is from 1 to infinity, and thus its total length is e/2, so because this is true for all e>0 it's also true for e=1/100 and thus i think ive solved it.
     
  5. Dec 22, 2006 #4

    verty

    User Avatar
    Homework Helper

    Ah, you are adding up an infinite number of infinitesimal subsets so that their union has an arbitrary finite length, am I right?
     
  6. Dec 22, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You're taking a union over what index set? I know you've got the answer, but try to write things properly. Is the union indexed by x? By k? What is the relationship between x and k?

    Question 2 looks ripe for the pigeonhole principle to me.
     
  7. Dec 22, 2006 #6
    the union is indexed by k.
    how exactly to use here the pigenhole principle?
     
  8. Dec 22, 2006 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No, he's taking the union of an infinite number of intervals, each with a positive length. And the total length is the infinite sum of the lengths which, in this case, is a geometric series.
     
  9. Dec 22, 2006 #8

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    If you were allowed to use each character once (I am assuming you meant "character" or "typographical symbol" when you wrote "letter"), then you'd have 5! = 720 permutations. (Just a guess.)
     
  10. Dec 22, 2006 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Is it? Then your answer is wrong. Since x doesn't vary at all, all you get is a nested union, i.e. the interval (x-e/2, x+e/2).

    As for part 2. How many numbers can you make from those symbols? Try vastly over estimating it. If you can just show there are fewer possible combinations than whatever that large number you wrote is then....
     
  11. Dec 23, 2006 #10
    then how should i correct my answer to the first question?
    so i shouldv'e indexed over x, for x in A?

    enumaelish wrote that there are 5! permutations, but you can use the symbols at least 10 times, so the number of combinations is 10C1+10C2+...+10C5 i think, am i wrong here?
     
  12. Dec 23, 2006 #11
    C is the binomial coefficient.
     
  13. Dec 23, 2006 #12
    Question 1 is best solved by simply observing that the result is true for any countable set.
     
  14. Dec 23, 2006 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The total sum of their lengths or the length of each one? The latter is easy, the former impossible!

    HOW MANY different such formulas are there?
     
  15. Dec 23, 2006 #14
    the length of each one.
    at least as many as there are simple numbers, but i dont know what's the upper bound.
     
  16. Dec 23, 2006 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The former; and it's not impossible, he's essentially solved it, he just needs to dot his i's and cross his t's.

    Your goal is to count the simple numbers by counting formulas, not the other way around.
     
    Last edited: Dec 23, 2006
  17. Dec 23, 2006 #16
    i dont think this is feasible to count all of the simple numbers from 1 to 10000000000.
    and anyway, who gurantees that a simple number has only one formula, maybe it can have two formuals which satisfy the condintions.

    and what do you mean dot his i's and cross his t's?
    what on hell i did wrong there, i shouldn't have indexed on k this i understand, cause then we have a nested interval, then i asked matt if i should have indexed over x, im waiting for his response.
     
  18. Dec 23, 2006 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You wrote

    [tex] \cup_{k \in \mathbb{N}} (x-e/2^k, x+e/2^k)[/tex]

    that is just (x-e/2,x+e/2). And has length e. You haven't said what x is. That is just an interval ov length e containing x. Unioning that over x isn't going to help you, is it? I mean

    [tex] \cup_{x \in A}(x-e/2^k, x+e/2^k)[/tex]

    doesn't work, since that is an infinite number of intervals all of length 2e/2^k, whatever k might now mean.



    You need to find one interval for each x in A, whose total length is e.
     
    Last edited: Dec 23, 2006
  19. Dec 23, 2006 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Who told you to count them? I told you to overestimate them. If you can show that there are at most 12 possible simple numbers then you're done right? A simple number is just specified by a string

    x_1,..,x_10 where the x_i are in that symbol list. How many such strings are there? Who cares if a number is represented by two different strings - you're not trying to count the number of simple numbers.
     
  20. Dec 23, 2006 #19
    but how estimate the number of simple numbers, i have 5 symbols, right?
    i can use all of them maximum 10 times, so the maximum number of them would be at least as the number 2222222222.
    i really dont know how to estimate their quantity.

    and for the first question, didnt i wrote: U(x-e/2^k+2,x+e/2^k+2)?
    perhaps, (x-e/2,x+e/2) for every x in A, is it that simple?
     
  21. Dec 23, 2006 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hrm, how did you get 2222222222?

    Incidentally, does the question say that a simple number uses up to 10 symbols, or up to 10 of each of the symbols? (p.s. there are 6 symbols)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Questions about coverings and some odd question.
Loading...