1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeonhole principle and counting

  1. Dec 7, 2007 #1
    1. The problem statement, all variables and given/known data
    1) 100 of the 5-element subsets of {1, . . . , Y } have the same SUM. (Fill in Y . Make Y as small as you can, however you need NOT prove that it is smallest possible. You might
    need a calculator.)

    2) Let FUNC be the set of all FUNCTIONS from N to N. Show that FUNC is NOT countable.

    2. Relevant equations
    Pigeonhole principle.


    3. The attempt at a solution
    1) The only thing I know is that I need to apply pigeonhole principle... Can someone give me a nudge?
    2) Definitely confused here. Since the integers are countable, the naturals must be countable too right? THen how the heck are I supposed to show that FUNC isn't countable when it is?
     
  2. jcsd
  3. Dec 11, 2007 #2
    a) Can you venture a guess as to what the pigeons and holes are?


    b)
    Natural numbers are countable, but that does not mean that all functions on N are countable. There are definitely an infinite number of functions mapping N to N, and there is no way to write them such that they could be counted.

    The set of all rational numbers is countable, even though there is an infinite gap between any two rational numbers. If the all the rational numbers were written in an [tex]\infty X \infty[/tex] array, they could be counted by the diagonals. No such rule exists for functions over N.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Pigeonhole principle and counting
  1. Counting Palindromes (Replies: 3)

  2. PigeonHole Help (Replies: 2)

Loading...