Subject: Analysis of sequences, number systems.
What you need to know:
principles of working with numbers written in positional number systems
Job example:
How many different character sequences of length 5 are there in the four-letter alphabet (A, C, G, T) that contain exactly two A's?
Decision:
1) consider various variants of words of 5 letters that contain two letters A and begin with A:
AA*** A*A** A**A* A***A
Here, the asterisk stands for any character from the set (C, G, T), that is, one of the three characters.
2) so, in each template there are 3 positions, each of which can be filled in three ways, so the total number of combinations (for each template!) is 33 = 27
3) total 4 patterns, they give 4 27 = 108 combinations
4) now we consider patterns where the first letter A is in the second position, there are only three of them:
*AA** *A*A* *A**A
they give 3 27 = 81 combinations
5) two patterns, where the first letter A is in the third position:
they give 2 27 = 54 combinations
6) and one pattern where the combination AA is at the end
they give 27 combinations
7) in total we get (4 + 3 + 2 + 1) 27 = 270 combinations
8) answer: 270.
Another example task:
How many words of length 5 beginning with a vowel can be formed from the letters E, G, E? Each letter can appear in a word several times. Words don't have to be meaningful words Russian language.
Decision:
1) the first letter of the word can be chosen in two ways (E or E), the rest - in three
2) the total number of distinct words is 2*3*3*3*3 = 162
3) answer: 162.
Solution (via formulas):
1) Given a word with a length of 5 characters like *****, where the red asterisk is a vowel (E or E), and the black letter is any of the three given.
2) The general formula for the number of options:
N = M L, where M is the cardinality of the alphabet, and L is the length of the code.
3) Since the position of one of the letters is strictly regulated (the multiplication sign in dependent events), the formula for all options will take the form: N=M 1L 1∙ M 2L2 ,
4) Then M 1 = 2 (vowel alphabet), and L 1 = 1 (only 1 position in a word).
M 2 = 3 (alphabet of all letters), and L 2 = 4 (the remaining 4 positions in the word).
5) As a result, we get: N= 21 ∙ 34 = 2 ∙ 81 = 162.
6) answer: 162.
Another example task:
All 4-letter words made up of the letters K, L, R, T are written in alphabetical order and numbered. Here is the beginning of the list:
1. KKKK
2. KKKL
3. KKKR
4. KKKT
Write down the word that is 67th from the top of the list.
Decision:
1) the simplest solution to this problem is the use of number systems; indeed, here the arrangement of words in alphabetical order is equivalent to the arrangement in ascending order of numbers written in the quaternary number system (the base of the number system is equal to the number of letters used)
2) perform the replacement K®0, L®1, R®2, T®3; since the numbering of words starts with one, and the first number KKKK®0000 is 0, the number 67 will be the number 66, which must be converted to the quaternary system: 66 \u003d 10024
3) After performing the reverse substitution (numbers for letters), we get the word LKKR.
4) Answer: LKKR.
Another example task:
All 5-letter words made up of the letters A, O, Y are written in alphabetical order.
Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Solution (1 way, iterate from the end):
5) calculate how many 5-letter words can be made up of three letters;
6) it is obvious that there are only 3 one-letter words (A, O, U); two letter words already 3´3=9 (AA, AO, AU, OA, OO, OU, UA, UO and UU)
7) similarly, it can be shown that there are only 35 = 243 words of 5 letters
8) it is obvious that the last, 243rd word is UUUUU
10) Answer: WOOOO.
2) write the beginning of the list, replacing the letters with numbers:
1. 00000
2. 00001
3. 00002
4. 00010
6) we replace numbers back with letters: 22212 ® UUUOU
7) Answer: WOOOO.
Solution (3 way, patterns in the alternation of letters,):
1) let's calculate how many 5-letter words can be made up of three letters:
35 = 243 words; 240th place - fourth from the end;
2) since the words are in alphabetical order, the first third (81 pieces) begin with "A", the second third (also 81) - with "O", and the last third - with "U", that is, the first letter changes through 81 words
3) similarly:
2nd letter changes after 81/3 = 27 words;
3rd letter - through 27/3 = 9 words;
4th letter - through 9/3 = 3 words and
The 5th letter changes in each line.
4) from this regularity it is clear that
The first position in the search word will be the letter "U" (the last 81 letters);
on the second - also the letter "U" (the last 27 letters);
on the third - also the letter "U" (the last 9 letters);
on the fourth - the letter "O" (because the last three letters are "U", and in front of them there are 3 letters "O")%
On the fifth - the letter "U" (because the last 3 letters alternate "A", "O", "U", and in front of them the same sequence).
5) Answer: WOOOO.
Another example of a task (author -):
All 5-letter words, composed of 5 letters A, K, L, O, W, are written in alphabetical order.
Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAL
4. AAAAO
5. AAAASH
6 . AAAKA
Where from the beginning of the list is the word SCHOOL?
Decision:
1) by analogy with the previous solution, we will use the quinary number system with the replacement A ® 0, K ® 1, L ® 2, O ® 3 and W ® 4
2) the word SCHOOL will be written in the new code as follows: 413205
3) we translate this number into the decimal system:
413205 = 4x54 + 1x53 + 3x52 + 2x51 = 2710
4) since the numbering of the elements of the list starts from 1, and the numbers in the quinary system start from zero, you need to add 1 to the result, then ...
5) Answer: 2711.
Another example task:
All 5-letter words made up of the letters A, O, Y are written in reverse alphabetically. Here is the beginning of the list:
1. uuuuu
2. WOOOO
3. WOOOO
4. Whoo
Write down the word that is 240th from the top of the list.
Solution (2nd way, ternary system, M. Gustokashin's idea):
1) according to the condition of the problem, it is only important that a set of three different characters is used, for which the order (alphabetic) is specified; therefore, for calculations, you can use any three characters, for example, the numbers 0, 1 and 2 (the order is obvious for them - in ascending order)
2) write out the beginning of the list, replacing the letters with numbers so that character order was reverse alphabetical(U → 0, O → 1, A → 2):
1. 00000
2. 00001
3. 00002
4. 00010
3) it resembles (in fact, it is so!) numbers written in the ternary number system in ascending order: the number 0 is in the first place, 1 is in the second, etc.
4) then it is easy to understand that the 240th place is the number 239, written in the ternary number system
5) translate 239 into the ternary system: 239 = 222123
6) replace numbers back with letters, considering reverse alphabetical order(0 → U, 1 → O, 2 → A): 22212 ® AAAOA
7) Answer: AAAA.
Tasks for training:
1) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Write down the word that is 101st from the beginning of the list.
2) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Write down the word that is 125th from the top of the list.
3) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Write down the word that is 170th from the top of the list.
4) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Write down the word that is 210th from the top of the list.
5) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5 . AAAKA
Write down the word that is 150th from the top of the list.
6) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5 . AAAKA
Write down the word that is 250th from the top of the list.
7) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5 . AAAKA
Write down the word that is 350th from the top of the list.
8) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5 . AAAKA
Write down the word that is 450th from the top of the list.
9) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
10) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
11) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Specify the number of the word WAUAU.
12) All 5-letter words made up of the letters A, O, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAO
3. AAAAU
4. AAAA
Enter the number of the first word that begins with the letter O.
13) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5. AAAA
Enter the number of the first word that begins with the letter U.
14) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5. AAAA
Enter the number of the first word that begins with the letter K.
15) All 5-letter words made up of the letters A, K, R, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5. AAAA
Specify the number of the word RUKAA.
16) All 5-letter words made up of the letters A, K, P, Y are written in alphabetical order. Here is the beginning of the list:
1. AAAAA
2. AAAAK
3. AAAAR
4. AAAAU
5. AAAA
Give the number of the word UKARA.
17) All 5-letter words made up of the letters K, O, P are written in alphabetical order and numbered. Here is the beginning of the list:
1. KKKKK
2. KKKKO
3. KKKKR
4. KKKOK
238 .
18) All 5-letter words made up of the letters I, O, Y are written in alphabetical order and numbered. Here is the beginning of the list:
1. IIIIII
2. IIIIIO
3. IIIIU
4. IIIII
Write down the word that is under the number 240 .
19) All 4-letter words composed of the letters M, A, R, T are written in alphabetical order. Here is the beginning of the list:
1. AAAA
2. AAAM
3. AAAR
4. AAAT
Write down the word that is 250 th place from the beginning of the list.
20) All 5-letter words made up of the letters P, O, K are written in alphabetical order and numbered. Here is the beginning of the list:
1. KKKKK
2. KKKKO
3. KKKKR
4. KKKOK
Write down the word that is under the number 182 .
21) How many words of length 4 starting with a consonant can be made from the letters L, E, T, O? Each letter can appear in a word several times. Words do not have to be meaningful words of the Russian language.
22) How many different character sequences of length 5 are there in the three-letter alphabet (K, O, T) that contain exactly two letters O?
23) How many different character sequences of length 6 are there in the three-letter alphabet (K, O, T) that contain exactly two letters K?
24) How many different character sequences of length 6 are there in a four-letter alphabet (M, A, P, T) that contain exactly two letters P?
Quest sources:
1. Training work of MIOO 2011-2012.
how many different character sequences of length 6 are there in a four-letter alphabet that contain exactly two identical letters"
Answers:
zero, because if you fix two identical letters, then the rest must be different. it turns out that only 3 letters remain in 4 positions, which is insufficient
Similar questions
- 7th grade PLEASE!! 1. A box with a load, with a volume of 1.6 m (3), is half immersed in sea water. What is the Archimedean force acting on it. 2. The weight of the ice floe is 22.5 kN. The ice floe is immersed in sea water at 2.27 m (3). What is the weight of a person on an ice floe. 3. Three immiscible liquids: water, kerosene, mercury - are poured into a vessel. In what order were they arranged? Justify the answer.
- 1. Life can be found: a) anywhere in the biosphere; b) anywhere on the Earth; c) anywhere in the biosphere, except for Antarctica and the Arctic. 2. The main difference between the biosphere and other shells of the Earth is that: a) no geochemical processes occur in the biosphere, but only biological evolution takes place; b) other sources of energy are used in the biosphere; c) geological and biological evolution proceed simultaneously. 3. What function of living matter can be attributed to the processes of photosynthesis: a) to gas; b) to redox; c) to concentration; d) to all the listed functions; e) to functions a) and b). 4. What is the limiting factor that most prevents the existence of life in the upper atmosphere? a) the composition of the air; b) temperature; c) ultraviolet radiation; d) humidity. 5. Which of the environmental factors most quickly affect changes in the biosphere: a) abiotic; b) anthropogenic; c) biotic. 6. Select the main environmental factors on which the prosperity of organisms in the ocean depends: a) the availability of water; b) the amount of precipitation; c) transparency of the environment; d) pH of the medium; e) salinity of the environment; e) the rate of evaporation of water; g) concentration of carbon dioxide in the medium. 7. Which of the factors affecting the atmosphere is the most constant? a) pressure; b) transparency; c) gas composition; d) temperature. 8. Why is it necessary to supply energy to the biosphere from the outside? a) because the carbohydrates formed in the plant serve as a source of energy for other organisms; b) because oxidative processes occur in organisms; c) because organisms destroy the remains of biomass. 9. The life of organisms in the soil can most likely be limited by: a) the amount of penetrating light; b) the amount of carbon dioxide in the soil; c) the amount of ground vegetation; d) the amount of precipitation. 10. All atmospheric oxygen is formed due to the activity of: a) autotrophic organisms; b) heterotrophic organisms; c) both autotrophic and heterotrophic organisms.
32) How many different character sequences of length 3 are there in the four-letter alphabet (A,B,C,D), if it is known that one of the neighbors of A is necessarily D, and the letters B and C never neighbor each other?
33) All 5-letter words made up of the letters P, O, R, T are written in alphabetical order and numbered. Here is the beginning of the list:
How many words are between the words AX and ROPOT (including these words)?
40) Alexey compiles a table of code words for transmitting messages, each message has its own code word. Aleksey uses 5-letter words as code words, in which there are only letters A, B, C, X, and the letter X may appear in the last place or not appear at all. How many different code words can Alex use?
51) Vasya makes up 5-letter words in which there are only letters K, A, T, E, P, and the letter P is used in each word at least 2 times. Each of the other valid letters can occur any number of times in the word, or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?
53) Vasya makes up 5-letter words, in which there are only letters M, U, X, A, and the letter U can be used no more than 3 times. Each of the other valid letters can occur any number of times in the word, or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?
55) Vasya makes up 6-letter words, in which there are only letters Zh, I, R, A, F, and the letter A is used in each word, but not more than 4 times. Each of the other valid letters can occur any number of times in the word, or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?
57) Vasya makes 6-letter words in which there are only letters P, I, R, O, G, and in each word there is one letter R, and after it there is always a vowel. Each of the other valid letters can occur any number of times in the word, or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?
59) Vasya makes up 5-letter words in which there are only letters P, I, R, O, G, and in each word the letter P can occur no more than two times, and if it exists, then after it there must be a vowel letter. Each of the other valid letters can occur any number of times in the word, or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?
61) Ivan makes up 5-letter words from the letters A, B, C, D, D, E, Yu, Ya. The first and last letters of this word can only be the letters E, Yu or Ya, in other positions these letters do not occur. How many different code words can Ivan make?
67) A palindrome is a character string that reads the same in both directions. How many different 6-character palindromes can be made from lowercase English letters? (There are 26 letters in the Latin alphabet).
