Question

In: Math

Let S be the set of natural numbers which can be written as a non-empty string...

Let S be the set of natural numbers which can be written as a non-empty string of ones followed by a non-empty string of zeroes. For example, 10, 111100 and 11100000 are all in S, but 11 and 1110011 are not in S. Prove that there exists a natural number n∈S, such that 2018 | n.

Solutions

Expert Solution

Consider the set { where the last number in the set contains 2019 such }.

There are 2019 numbers in the set . Now, we consider their remainders when divided by . See that when any number is divided by , the possible remainders are {i.e. there are 2018 possible remainders}. Since has 2019 numbers, by the Pigeonhole Principle at least two of the numbers in give the same remainder when divided by .

Let those numbers be and . Then we have

i.e. when divides then the remainder is .

i.e. { where }.

Note that the difference between any two numbers in the set is of the form { i.e. a string of followed by a string of , which are precisely the elements of }.

So . Put . Then we have an such that .

This completes our proof.

milcah answered 1 year ago

Next > < Previous

Related Solutions

Let S be a non-empty set (finite or otherwise) and Σ the group of permutations on...

Let S be a non-empty set (finite or otherwise) and Σ the group of permutations on S. Suppose ∼ is an equivalence relation on S. Prove (a) {ρ ∈ Σ : x ∼ ρ(x) (∀x ∈ S)} is a subgroup of Σ. (b) The elements ρ ∈ Σ for which, for every x and y in S, ρ(x) ∼ ρ(y) if and only if x ∼ y is a subgroup of Σ.

Let S be the set of all natural numbers that are describable in English words using...

Let S be the set of all natural numbers that are describable in English words using no more than 50 characters (so, 240 is in S since we can describe it as “two hundred forty”, which requires fewer than 50 characters). Assuming that we are allowed to use only the 27 standard characters (the 26 letters of the alphabet and the space character), show that there are only finitely many numbers contained in S. (In fact, perhaps you can show...

Let S be a set of n numbers. Let X be the set of all subsets...

Let S be a set of n numbers. Let X be the set of all subsets of S of size k, and let Y be the set of all ordered k-tuples (s1, s2, , sk) such that s1 < s2 < < sk. That is, X = {{s1, s2, , sk} | si S and all si's are distinct}, and Y = {(s1, s2, , sk) | si S and s1 < s2 < < sk}. (a) Define a one-to-one correspondence f : X → Y. Explain...

Assume you already have a non-empty string S, which is guaranteed to contain only digits 0...

Assume you already have a non-empty string S, which is guaranteed to contain only digits 0 through 9. It may be of any length and any number of digits may occur multiple times. Starting from the front of the string, write a loop that jumps through the characters in the string according to the following rule: Examine the current character and jump that many characters forward in the string Stop if you jump past the end of the string, or...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that X / R is a partition of X.

let R be a ring; X a non-empty set and (F(X, R), +, *) the ring...

let R be a ring; X a non-empty set and (F(X, R), +, *) the ring of the functions from X to R. Show directly the associativity of the multiplication of F(X, R). Assume that R is unital and commutative. show that F(X, R) is also unital and commutative.

Let the cardinal number of N, the set of all natural numbers, be א0. Prove that...

Let the cardinal number of N, the set of all natural numbers, be א0. Prove that the product set N × N = {(m,n);m ∈ N,n ∈ N} has the same cardinal number. Further prove that Q+, the set of all positive rational numbers, has the cardinal number N_0. Hint: You may use the formula 2^(m−1)(2n − 1) to define a function from N × N to N, see the third example on page 214 of the textbook.

Let X be a non-empty set and P(X) its power set. Then (P(x), symetric difference, intersection)...

Let X be a non-empty set and P(X) its power set. Then (P(x), symetric difference, intersection) is a ring. Find a non-trivial ideal of P(X).

In C++ Consider the language L = { s$s' : s is a possibly empty string...

In C++ Consider the language L = { s$s' : s is a possibly empty string of characters other than $ , s' = reverse( s )} as defi ned in Chapter 6 . Write a recognition algorithm for this language that uses both a queue and a stack. Thus, as you traverse the input string, you insert each character of s into a queue and each character of s' into a stack. Assume that each input string contains exactly...

The number 81 is written as a sum of three natural numbers 81 = a +...

The number 81 is written as a sum of three natural numbers 81 = a + b + c (the triple (a,b,c) is ordered; e.g., the decompositions 81 = 1 + 1 + 79 and 81 = 1 + 79 + 1 are different. Also, assume that all the decompositions have equal probability.) What is the probability that there exists a triangle with sides a, b, and c? (PLEASE EXPLAIN THE STEPS AND WHY YOU KNOW TO DO STEPS, THANKS)

Subjects