retagged by
12,384 views
60 votes
60 votes

Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is _______.

retagged by

6 Answers

Best answer
94 votes
94 votes
For a function from set $A$ to set $B$, we need to have a mapping for all elements of $A$ and mapping must be unique.
Let number of elements in $A$ be $m$ and that in $B$ be $n$

So, if we consider an element from $A,$ it can be mapped to any of the element from $B.$ i.e., it has $n$ possibilities when a function is formed. Similarly, for all other members also there are $n$ possibilities as one element from $A$ can be mapped to  only a single element in $B$ (though reverse need not true). So, for $m$ elements in $A,$ we totally have $\underbrace{n \times \dots \times n}_{m \text{ times}} = n^m$ possible functions.

In the question Number of elements (functions) in $f$ is $2^{2^4}$ as $\{0,1\}^4$ contains $2^4$ elements. So, number of functions from $S$ to $\{0,1\}$ will be $2^{2^{2^4}}$. So, $\log_2 \log_2 N = 2^4 = 16.$
edited by
69 votes
69 votes

Answer : 16

16 votes
16 votes

If anybody wondering why it is 2^2^16 and not just 2^16, here is explanation.

From above two answer number of functions are 2^16 .{f1 , f2 , f3 , f4, ...............f2^16}

And if you read question carefully they asking number of functions from S to the set {0,1}

and set S is .{f1 , f2 , f3 , f4, ...............f2^16} which has to mapped to set {0, 1}

Therefore answer is 2^2^16.

I have written this answer according to my understanding , please correct me if i am wrong

14 votes
14 votes

Number of functions in S is 2^16 so in N is (2^(2^16)), and value of  loglog n will be 16.

Answer:

Related questions

31 votes
31 votes
6 answers
2
gatecse asked Sep 15, 2014
8,643 views
When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created wit...
7 votes
7 votes
2 answers
3
go_editor asked Jul 1, 2016
3,675 views
Let $\text{A}$ be a finite set having $x$ elements and let $\text{B}$ be a finite set having $y$ elements. What is the number of distinct functions mapping $\text{B}$ int...