Using the pigeonhole theorem prove that any set of 220 10-character strings over the alphabet {a,b,c,d}...

Using the pigeonhole theorem prove that any set of 220 10-character strings over the alphabet {a,b,c,d} contains a pair of anagrams.

Solutions

Expert Solution

So the maximal set with no anagram pairs contain 286 strings. Which means there are some sets containing 220 strings such that the set doesn't contain any pair of anagrams.

I have used the formulas in the last calculation.

I don't think I have done any mistake. If you find any please comment. Otherwise the question is wrong, pigeonhole theorem can't be used here , to use that we need a set containing 287 or more strings.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Prove the following using any method you like: Theorem. If A, B, C are sets, then...

Prove the following using any method you like: Theorem. If A, B, C are sets, then (A ∪ B) \ C = (A \ C) ∪ (B \C) and A ∪ (B \ C) = (A ∪ B) \ (C \ A)

Passwords of length 10 are formed using the character set S = {a, b, c, …,...

Passwords of length 10 are formed using the character set S = {a, b, c, …, z, A, B, …, Z, 0, 1, 2, .., 9}. Thus the set S consists of 62 different characters. For each part below, you must include a few words that describe your counting strategy. (a) How many passwords of length 10 use the character Q exactly two times? (b) How many passwords of length 10 use at most one of the “upper case” letters...

Prove that the set R ={ a+ b√2+c√3+d√6 , a,b,c,d belongs to Q } is a...

Prove that the set R ={ a+ b√2+c√3+d√6 , a,b,c,d belongs to Q } is a field

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x,...

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x, y} where 2 * (# of x's) = 3 * (#y's) That is, if we let nx be the number of x's and ny be the number of y's, then the strings in these language are those where 2nx = 3ny Try to find a PDA that is as simple and elegant as possible (do not convert from CFG). ------------------------------------------------------------------------------------------------------------------ USE Notation between transition:...

S is the language over S = {a, b, c, d, e} containing all strings that...

S is the language over S = {a, b, c, d, e} containing all strings that start with at least 2 a's, followed by any number of b's, followed by 5 c's, followed by an odd number of d's, followed by an even number of e's. For example, S contains aaabbcccccdee, aaaacccccdddeeee, and so on. Write S symbolically in the manner of section 6.1, problem # 12 a) - f). Example 6.12 will also be helpful. bonus: How many strings in {000, 11}*...

3. Are the following languages A and B over the alphabet Σ = {a, b, c,...

3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonregular? • For a language that is regular, give a regular expression that defines it. • For a nonregular language, using the pumping lemma prove that it is not regular. (a) A = {d 2j+1c k+1 | j ≥ k ≥ 0} · {c r+2b 2s+3 | r ≥ 0 and s ≥ 0} (b) B = {a 2j+2b k+3c j+1...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet {a, b} defined inductively as follows: • Base case: the empty word λ and the word a belong to S • Inductive rule: if ω is a string of S then both ω b and ω b a belong to S as well. 1. Prove that if a string ω belongs to S, then ω does not have two or more consecutive a’s. 2....

prove that a compact set is closed using the Heine - Borel theorem

Suppose the alphabet is S = {A B C D} and the known probability distribution is...

Suppose the alphabet is S = {A B C D} and the known probability distribution is PA = 0.3, PB = 0.1, PC = 0.5, and PD = 0.1. Decode the Huffman coding result {11000010101110100} to the original string based on the probability distribution mentioned above. The codeword for symbol “D” is {111}. Please writing down all the details of calculation.

Bezout’s Theorem and the Fundamental Theorem of Arithmetic 1. Let a, b, c ∈ Z. Prove...

Bezout’s Theorem and the Fundamental Theorem of Arithmetic 1. Let a, b, c ∈ Z. Prove that c = ma + nb for some m, n ∈ Z if and only if gcd(a, b)|c. 2. Prove that if c|ab and gcd(a, c) = 1, then c|b. 3. Prove that for all a, b ∈ Z not both zero, gcd(a, b) = 1 if and only if a and b have no prime factors in common.

Subjects