Monday, December 17, 2018

Shooting problem 211 from ege18.doc via Technique of calculating basic predicates



We intend to solve Problem 211 from ege18.doc via  Technique of calculating  basic predicates  developed by E.A. Mironchick in manuscript http://kpolyakov.spb.ru/download/mea18bit.pdf 
Graphics using circles and a universal set in the original article allows you to implement alternative solutions quite effectively. The example below shows this very well. See also http://mapping-metod.blogspot.com/2017/08/bitwise2-18.html
for solution of same problem via Bitwise2.
See Problem 211 from ege18.doc itself
Determine the number of positive integers A such that
((x&17¬ = 0)=>((x&A¬ =0)=>(x&58¬ =0)))=>((x&8 = 0)^(x&A¬ = 0 )^(x&58 = 0))
is identically false (that is, it takes the value 0 
for any natural value of the variable x)?
 

Original source of problem 211



(E(17) => (E(A) => E(58))) => (¬E(8)*E(A)*¬E(58)) = 0
¬(E(17) => (E(A) => E(58))) + (¬E(8)*E(A)*¬E(58)) = 0
(¬E(17) + ¬E(A) + E(58)) * ¬(¬E(8)*E(A)*¬E(58)) = 1
(¬E(17) + ¬E(A) + E(58)) * (E(8) + ¬E(A) + E(58)) = 1


Hence getting system

¬E(17) + ¬E(A) + E(58) = 1  (1)
 E(8)  + ¬E(A) + E(58) = 1    (2)

E(A) => E(58) + ¬E(17) = 1  (1)
E(A) => E(58) + E(8) = 1      (2)

(E(A) => E(58)) + (E(A) => ¬E(17)) = 1  (1)
(E(A) => E(58)) + (E(A) => E(8)) = 1      (2)

Thus A(max) = 58

Now we address the question been asked in the body of problem 211
via techique of calculating basic predicates

E(58) = E(32) + E(16) + E(8) + E(2)


1. E(2) defines    2
2. E(8) defines   8
3. E(2)⋃E(8) defines 10
4. E(16) defines 16
5. E(16)⋃E(2) defines  18
6. E(16)⋃E(8) defines  24
7. E(16)⋃E(8)⋃E(2) defines  26
8. E(32) defines  32
9. E(32)⋃E(2) defines  34
10.E(32)⋃E(8) defines  40
11.E(32)⋃E(8)⋃E(2) defines  42
12.E(32)⋃E(16) defines  48
13.E(32)⋃E(16)⋃E(2) defines  50
14.E(32)⋃E(16)⋃E(8) defines  56
15.E(32)⋃E(16)⋃E(8)⋃E(2) defines  58

Answer = {2,8.10,16,18,24,26,32,34,40,42,48,50,56,58}

Let us call number of combinations of n by m C(n,m)
Then we get C(4,1)+C(4,2)+C(4,3)+C(4,4) = 4+6+4+1 = 15

References
1. Множества в задачах с анализом битовых цепочек /Л.Л.Босова, Е.А. Мирончик//Информатика в школе /2017. No 7(130). С. 45-48.

No comments:

Post a Comment