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

Thread: 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
    $\displaystyle |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 $\displaystyle m$ does $\displaystyle a_m\equiv a_{m+1}$.
    This means the inequalities must be strict:
    $\displaystyle |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 $\displaystyle |S(a_0)| < 0 $.

    This means the initial assumption was incorrect, and there must exist an $\displaystyle m$ s.t. $\displaystyle 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
    $\displaystyle |S(a_0)| < |S(a_1)| < |S(a_2)| < \dots < |S(a_{2^n+1})| \leq 2^n$
    Since $\displaystyle |S(a_i)|$ are integers, we must have $\displaystyle |S(a_i)| + 1 \leq |S(a_{i+1})|$.
    From this, you can use induction to prove:
    $\displaystyle |S(a_0)| + 2^n + 1 \leq |S(a_{2^n+1})| \leq 2^n$
    so $\displaystyle |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,577
    Thanks
    790
    Basically, you start with a nonnegative number (the number of elements in $\displaystyle S(a_0)$). Then you make $\displaystyle 2^n + 1$ steps. In each step, you increase the number. (All numbers are integers.) If after $\displaystyle 2^n+1$ steps you have a number that is at most $\displaystyle 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: Oct 4th 2011, 06:34 AM
  2. Help with logic problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 10th 2010, 04:37 PM
  3. Logic problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 17th 2009, 07:19 PM
  4. Logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 24th 2007, 06:58 AM
  5. another logic problem....PLEASE HELP
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 21st 2007, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum