Page 2 of 2 FirstFirst 12
Results 16 to 18 of 18

Math Help - Propotional Logic Problem

  1. #16
    Newbie
    Joined
    Dec 2010
    Posts
    15
    Quote Originally Posted by snowtea View Post
    You already have everything.

    The basic idea is you are using proof by contradiction.
    You know for a fact that
    |S(a_0)| \leq |S(a_1)| \leq |S(a_2)|\leq\dots\leq |S(a_{2^n+1})|\leq2^n

    Now, assume that for no m does a_m\equiv a_{m+1}.
    This means the inequalities must be strict:
    |S(a_0)| < |S(a_1)| < |S(a_2)| < \dots < |S(a_{2^n+1})| \leq 2^n

    But this lead to a contradiction because this forces |S(a_0)| < 0 .

    This means the initial assumption was incorrect, and there must exist an m s.t. a_m\equiv a_{m+1}.
    Could you tell me how can i say that..i dont remember very well the sequences.
    Again thank you both..a loooooooooooot
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    |S(a_0)| < |S(a_1)| < |S(a_2)| < \dots < |S(a_{2^n+1})| \leq 2^n
    Since |S(a_i)| are integers, we must have |S(a_i)| + 1 \leq |S(a_{i+1})|.
    From this, you can use induction to prove:
    |S(a_0)| + 2^n + 1 \leq |S(a_{2^n+1})| \leq 2^n
    so |S(a_0)| \leq -1
    size of a set cannot be negative (contradiction).
    Follow Math Help Forum on Facebook and Google+

  3. #18
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Basically, you start with a nonnegative number (the number of elements in S(a_0)). Then you make 2^n + 1 steps. In each step, you increase the number. (All numbers are integers.) If after 2^n+1 steps you have a number that is at most 2^n, then you can win the Fields medal.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: October 4th 2011, 06:34 AM
  2. Help with logic problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 10th 2010, 04:37 PM
  3. Logic problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 17th 2009, 07:19 PM
  4. Logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 24th 2007, 06:58 AM
  5. another logic problem....PLEASE HELP
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2007, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum