**Find Detailed Video Solution:**

Dark Mode

440 views

2 votes

Let $\text{S}$ be the set of all bit-strings of length $7 .$ We define a relation $\mathrm{R}$ on the set $\mathrm{S}$ by the rule that $x\mathrm{R}y$ iff $x$ and $y$ differ in exactly one bit position i.e., if $x=x_{1} x_{2} \ldots x_{7}$ and $y=y_{1} y_{2} \ldots y_{7}$, then $x\mathrm{R}y$ iff there is an $i$ such that $\forall j \neq i, x_{j}=y_{j}$ and $x_{i} \neq y_{i}$.

What is the cardinality of relation $\mathrm{R}$?

What is the cardinality of relation $\mathrm{R}$?

2 votes

If we make the graph of R, we get a hypercube graph with $2^{7}$ vertices, degree of each vertex being $7.$ Number of edges in this graph will be $7 \times 2^{6}$. Every edge contributes $2$ ordered pairs in relation $\mathrm{R}$, hence, number of ordered pairs in $\mathrm{R}=2 \times 7 \times 2^{6}=896$.

**Hypercubes:**

Recall that the set of all $n$-bit strings is denoted by $\{0,1\}^{n}$. The $n$-dimensional hypercube is a graph whose vertex set is $\{0,1\}^{n}$ (i.e., there are exactly $2^{n}$ vertices, each labeled with a distinct $n$-bit string), and with an edge between vertices $x$ and $y$ iff $x$ and $y$ differ in exactly one bit position. I.e., $x=x_{1} x_{2} \ldots x_{n}$ and $y=y_{1} y_{2} \ldots y_{n}$, then there is an edge between $x$ and $y$ iff there is an $i$ such that $\forall j \neq i, x_{j}=y_{j}$ and $x_{i} \neq y_{i}.$

The total number of edges in an $n$-dimensional hypercube is $n \times 2^{n-1}$.

**Find Video Solution:**

1 vote

**Answer: $2^7*7$**

Relation $R$ is on set $S$ simply means that $R$ is a relation from $S → S$, for $2$ length bit strings $S = \begin{Bmatrix} 00, 01, 10, 11 \end{Bmatrix}$. The graph would be like that. There are some things that we can analyze here:

- Each vertex has degree $n$.
- Total vertices in a partition are $2^n$.

So for $n$ vertices total edges would be $2^n*n$

This answer is correct. It is a graph with $2^{n+1}$ vertices because there are two copies of set $S$ are present with one copy of S per partition and relation $R$ is satisfying across the partitions, not within the partition.

And, things which I had thought were missing, added as a comment.

Though idea is similar to find edges in hypercube graph but representation is different here. This is a nice approach which might help to solve other questions as well. (+1)

And, things which I had thought were missing, added as a comment.

Though idea is similar to find edges in hypercube graph but representation is different here. This is a nice approach which might help to solve other questions as well. (+1)

0

0 votes

The question asks for number of pairs (x,y) in which the x and y are 7 bit strings of 0 and 1. and they must differ in exactly one position

We can solve this using combinatorics approach. each position in the pair of strings has 4 choices

{00,01,10,11}

Now first select a position to keep the bit same in 7 ways since 7 bit string is given.

To keep this bit different we have two choices {01,10}.

Now we are left with 6 positions and they must be same, so now again for each of 6 bits we have two choices {00,11}

so 2^6 choices for 6 bits left.

So total no. of ways is 7*2*2^6 = 896

We can solve this using combinatorics approach. each position in the pair of strings has 4 choices

{00,01,10,11}

Now first select a position to keep the bit same in 7 ways since 7 bit string is given.

To keep this bit different we have two choices {01,10}.

Now we are left with 6 positions and they must be same, so now again for each of 6 bits we have two choices {00,11}

so 2^6 choices for 6 bits left.

So total no. of ways is 7*2*2^6 = 896