Monday, November 26, 2018

Proof of core sample of E.A. Mironchik's "Solving problems EGE-18 with per bit operations " (2017) via Bitwise2

First what we would have to use comes from Polyakov's ege18.doc


Sample as is 
See Решение задания ЕГЭ - 18 с битовыми операциями


(x&26 ¬=10 ) = ¬Z(16) + Z(8) + Z(2)
(x&27 = 11 )   =   Z(16)*¬Z(8)*¬Z(2)*¬Z(1)

26 = 11010 
10 = 01010
27 = 11011
11 = 01011

Due to
  ¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
    A + ¬A*B = (A + ¬A)*(A + B) = A + B   
After applying conversions mentioned above
We are going to obtain via Polyakov's formulas  :-

¬Z(16) + Z(8) + Z(2) +  Z(16)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1
¬Z(16) + Z(8) +  Z(2) + ¬Z(1) + A = 1
¬(Z(16)*Z(1)) + Z(8) + Z(2) + A = 1
Z(16 OR 1) => Z(8) + Z(2) + A = 1
(Z(17)=> A) + (Z(17)=>Z(8)) + (Z(17)=>Z(2)) = 1
Z(17) => A = 1

Thus A(max) = 17

So issue when "b1-c1=b2-c2" might be resolved via Bitwise2 technique and Problem 5 gets resolved without any new development efforts.
Also notice that in general (b-c) doesn't have to be a basic predicate. Sample bellow has (b-c) = 96. But the multitude of "c" bits "1"  must be included in the multitude of "b" bits "1"

********************
Another samples
********************
Here we sequentially apply

¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
     A + ¬A*B = (A + ¬A)*(A + B) = A + B 

***************************************************
(x&248 ¬= 152) v (x&252 = 156) v (x&A = 0) = 1
***************************************************

252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000

(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 =  156) =  Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)

¬Z(96) + Z(128) + Z(16) + Z(8) + 

               Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + A =  1
¬(Z(96)*Z(4))   + Z(128) + Z(16) + Z(8) + A = 1
Z(100) => Z(128) + Z(16) + Z(8) + A = 1
(Z(100)=>Z(128)) + (Z(100)=>Z(16)) + (Z(100)=>Z(8)) + 

              (Z(100)=>A) = 1
Z(100) => A = 1

Thus A(max) = 100


****************************************************************
(x&248 ¬= 152)v(x&252 = 156)v(x&250 = 154)v(x&A = 0) = 1
****************************************************************
252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000
250 = 11111010
154 = 10011010

(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 =  156) =  Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
(x&250 =  154) =  Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2)

¬Z(96) + Z(128) + Z(16) + Z(8) + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
       + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1


Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (1)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4)
       + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2)  + A =  1


Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (2)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + ¬Z(2)  + A =  1


Now we are ready to apply De Morgan rules :-
     ¬(Z(96)*Z(4)*Z(2)) + Z(128) + Z(16) + Z(8) + A = 1

Finally getting done
Z(102) => Z(128) + Z(16) + Z(8) + A = 1
(Z(102)=>Z(128)) + (Z(102)=>Z(16)) + (Z(102)=>Z(8)) + (Z(102)=>A) = 1
Z(102) => A = 1

Thus A(max) = 102
 

*****************************************************
(x&252 ¬= 188) v (x&248 = 184) v (x&A = 0) = 1
*****************************************************

252 = 11111100
188 = 10111100
248 = 11111000
184 = 10111000
 

Here we sequentially apply

¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
     A + ¬A*B = (A + ¬A)*(A + B) = A + B

(x&252 ¬= 184) = ¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8)
(x&248 = 188)  = Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4)

¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) + 

            Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(64)*Z(4))  + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
Z(68) => + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
(Z(68)=>Z(128)) + (Z(68)=>Z(32)) + (Z(68)=>Z(16)) + 

           (Z(68)=>Z(8)) + (Z(68)=>A) = 1
Z(68) => A = 1

Thus A(max) = 68



No comments:

Post a Comment