1

A man has (2n+1) friends.The number of ways in which he can invite atleast n+1 friends for dinner is 4096.Find the number of friends of the man

Options given:

1) $11$ 2) $13$ 3) $15$ 4) $17$

My Approach:

I did $2$^$(2n+1)$ -$1$=$2$^$12$

I am not getting the right Ans.Can anyone give me the hint about what mistake i did to solve the problem?

justin takro
  • 1,288

1 Answers1

3

Note that if $A$ is a set of at least $n+1$ friends, then there are at most $n$ friends not in $A$. For each set of friends that he can invite there is therefore a set that he cannot invite (because it’s too small). Thus, $4096$ is exactly half of the number of all subsets of his set of friends: half of the sets have at least $n+1$ members, and the other half have at most $n$ members. Since he has $2n+1$ friends, there are $2^{2n+1}$ sets of friends, and half of that number is $2^{2n}$. Thus, $2^{2n}=4096=2^{12}$, $2n=12$, $n=6$, and he has $2\cdot6+1=13$ friends.

Brian M. Scott
  • 616,228
  • M.Scott I have not understood your Answer . – justin takro Sep 27 '15 at 17:55
  • @justin: Let $F$ be his set of friends. If $A\subseteq F$ is a set that he can invite, then $F\setminus A$ is a set that he cannot invite, and vice versa. This is gives us a bijection between the sets that are big enough to be invited and the sets that are too small to be invited. That means that exactly half of the possible sets of friends are big enough to be invited, and the other half are too small. There are altogether $2^{2n+1}$ subsets of $F$; half of that is $2^{2n}$, so there are $2^{2n}$ sets of friends big enough to invite. But we know that there are $4096$ such sets, so ... – Brian M. Scott Sep 27 '15 at 17:59
  • ... $2^{2n}=4096$. The rest is just arithmetic. – Brian M. Scott Sep 27 '15 at 17:59