recategorized by
907 views
2 votes
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}$?
recategorized by

3 Answers

2 votes
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:

https://youtu.be/tqjuxfutFHg?t=1384

edited by
1 votes
1 votes

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:

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

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

0 votes
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
edited by
Answer:

Related questions