Some issues related with Unified State Examination in Informatics in Russian Federation

Sunday, November 25, 2018

Bitwise2 vs E.A. Mironchik "Solving problems EGE-18 with per bit operations " (2017)

Treat problem 5 from original manuscript
"Решение задания ЕГЭ - 18 с битовыми операциями" with Bitwise2

Follow Bitwise2 rules

(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 :-

¬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) = 36. But the multitude
of "c" bits "1" must be included in the multitude of "b" bits "1"

First notice

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

and follow "Решение задания ЕГЭ - 18 с битовыми операциями"

***********************************
For instance consider equation
***********************************

(x&46 ¬= 10) v (x&47 = 11) v (x&A =0) = 1
(x&47 = 11) = ¬E(36)*E(8)*E(2)*E(1)
(x&46 ¬= 10) = E(36) + ¬E(8) + ¬E(2)

Hacking "mysterious" rules of Boolean algebra ( fragment of original
manuscript posted bellow )

According Boolean algebra rules (1),(2) :-

Per (1)

E(36) + ¬E(8) + ¬E(2) + ¬E(36)*E(8)*E(2)*E(1)+¬E(A) = 1
E(36) + ¬E(8) + ¬E(2) + ¬E(36)*E(2)*E(1) + ¬E(A) = 1
E(36) + ¬E(8) + ¬E(2) + ¬E(36)*E(1) + ¬E(A) = 1

Per (2)

E(36) + ¬E(8) + ¬E(2) + E(1) + ¬E(A) = 1

46= 101110 (binary)
10 =001010
47 =101111
11 =001011

Now we see that A(max) = 37

**************************************
Another sample done both ways
**************************************

(x&62 ¬= 26)v(x&63 = 27)v(x&A = 0) = 1

62 = 111110
26 = 011010

63 = 111111
27 = 011011

(x&63 = 27) = ¬E(36)*E(16)*E(8)*E(2)*E(1)
(x&62 ¬= 26) = E(36) + ¬E(16) + ¬E(8) + ¬E(2)
E(36) + ¬E(16) + ¬E(8) + ¬E(2) + ¬E(36)*E(16)*E(8)*E(2)*E(1) + ¬E(A) = 1
E(36) + ¬E(16) + ¬E(8) + ¬E(2) + E(1) + ¬E(A) = 1
E(37) + ¬E(16) + ¬E(8) + ¬E(2) + E(1) + ¬E(A) = 1

Thus A(max) = 37
*********************
Bitwise solution
*********************
(x&62 ¬= 26)v(x&63 = 27)v(x&A = 0) = 1

62 = 111110
26 = 011010

63 = 111111
27 = 011011

(x&63 = 27) = Z(36)*¬Z(16)*¬Z(8)*¬Z(2)*¬Z(1)
(x&62 ¬= 26) = ¬Z(36) + Z(16) + Z(8) + Z(2)
¬Z(36) + Z(16) + Z(8) + Z(2) + Z(36)*¬Z(16)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1
¬Z(36) + Z(16) + Z(8) + Z(2) + ¬Z(1) + A = 1
¬(Z(36)*Z(1)) + Z(16) + Z(8) + Z(2) + A = 1
Z(37) => Z(16) + Z(8) + Z(2) + A = 1

(Z(37)=>A) + (Z(37)=>16) + (Z(37)=>Z(8)) + (Z(37)=>Z(2)) = 1

Thus A(max) = 37

********************************
Keep staying with Bitwise
********************************
(x&62 = 30)v(x&60 ¬= 28)v(x&A = 0) = 1

62 = 111110
30 = 011110
60 = 111100
28 = 011100

(x&62 = 30) = Z(32)*¬Z(16)*¬Z(8)*¬Z(4)*¬Z(2)
(x&60 ¬= 28) = ¬Z(32) + Z(16) + Z(8) + Z(4)
¬Z(32) + Z(16) + Z(8) + Z(4) + Z(32)*¬Z(16)*¬Z(8)*¬Z(4)*¬Z(2) +A = 1
¬Z(32) + Z(16) + Z(8) + Z(4) + ¬Z(2) + A = 1
¬(Z(32)*Z(2)) + Z(16) + Z(8) + Z(4) + A = 1
Z(34) => Z(16) + Z(8) + Z(4) + A = 1
(Z(34)=>Z(16)) + (Z(34)=>Z(8)) + (Z(34)=>Z(4)) + (Z(34)=>A) = 1
Z(34)=>A = 1

Thus A(max) = 34

*******************************************************
(x&120 ¬= 56) v (x&124 = 60) v (x&A=0) = 1
*******************************************************
120 = 1111000
56 = 0111000
124 = 1111100
60 = 0111100

(x&120 ¬= 56) = ¬Z(64) + Z(32) + Z(16) + Z(8)
(x&124 = 60) = Z(64)*¬Z(32)*Z(16)*¬Z(8)*¬Z(4)

(x&120 ¬= 56) v (x&124 = 60) v A =
¬Z(64) + Z(32) + Z(16) + Z(8) + Z(64)*¬Z(32)*Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(64) + Z(32) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(64)*Z(4)) + Z(32) + Z(16) + Z(8)   + A = 1
¬(Z(64 OR 4)) + Z(32) + Z(16) + Z(8) + A = 1
¬Z(68) + Z(32) + Z(16) + Z(8) + A = 1
Z(68) => Z(32) + Z(16) + Z(8) + A = 1
(Z(68) => Z(32)) + (Z(68)=>Z(16)) + (Z(68)=>Z(8)) + (Z(68)=> A) = 1
Z(68) => A = 1

Thus A(max)=68

************************************************************
(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(64)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
       + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1

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

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

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

Wednesday, November 21, 2018

What is interesting in the work of E.A. Mironchik "Solving problems EGE-18 with per bit operations " (2017) ?

******************************
UPDATE as of 24/11/2018
******************************
Treat problem 5 from original manuscript
http://kpolyakov.spb.ru/download/mea18bit.pdf with Bitwise2

Follow Bitwise2 rules

(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 :-

¬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.

**********************
END UPDATE
**********************
First notice and follow http://kpolyakov.spb.ru/download/mea18bit.pdf

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

***********************************
For instance consider equation
***********************************

(x&46 ¬= 10) v (x&47 = 11) v (x&A =0) = 1
(x&47 = 11) = ¬E(36)*E(8)*E(2)*E(1)
(x&46 ¬= 10) = E(36) + ¬E(8) + ¬E(2)

Hacking mysterious rules of Boolean algebra ( fragment of original
manuscript posted bellow )

********************************
Keep staying with Bitwise
********************************
(x&62 = 30)v(x&60 ¬= 28)v(x&A = 0) = 1

62 = 111110
30 = 011110
60 = 111100
28 = 011100

(x&62 = 30) = Z(32)*¬Z(16)*¬Z(8)*¬Z(4)*¬Z(2)
(x&60 ¬= 28) = ¬Z(32) + Z(16) + Z(8) + Z(4)
¬Z(32) + Z(16) + Z(8) + Z(4) + Z(32)*¬Z(16)*¬Z(8)*¬Z(4)*¬Z(2) +A = 1
¬Z(32) + Z(16) + Z(8) + Z(4) + ¬Z(2) + A = 1
¬(Z(32)*Z(2)) + Z(16) + Z(8) + Z(4) + A = 1
Z(34) => Z(16) + Z(8) + Z(4) + A = 1
(Z(34)=>Z(16)) + (Z(34)=>Z(8)) + (Z(34)=>Z(4)) + (Z(34)=>A) = 1
Z(34)=>A = 1

Thus A(max) = 34

*******************************************************
(x&252 = 188) v (x&248 ¬= 184) v (x&A = 0) = 1
*******************************************************
252 = 11111100
188 = 10111100
248 = 11111000
184 = 10111000

(x&248 ¬= 184) = ¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8)
(x&252 = 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

*************************************************************
(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

*************************************************************************
Pick up 228 from ege18.doc and follow Bitwise2 extended schema
*************************************************************************
((x & A ¬= 0) => (x & 55=33)) + (x & 112¬=16) = 1
A + Z(22)¬Z(32)¬Z(1) + ¬Z(96) + Z(16) = 1
Z(96) = > A + Z(22)¬Z(32)¬Z(1) + Z(16) = 1

Finally we get

(Z(96 =>A)+(Z(96)=>Z(22))*(Z(96)=>¬Z(32))*(Z(96)=>¬Z(1))+(Z(96)=> Z(16)) = 1

Due to implication is distributive against conjunction and (Z(96)=>Z(22)) = 0
Z(96) => A = 1

Thus A(max) =96

**********************************
Attempt same approach for
**********************************

(x&46 ¬= 10) v (x&47 = 11) v (x&A =0) = 1
¬Z(36) + Z(8) + Z(2) + Z(36)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1
Z(36) => Z(8) + Z(2) + Z(36)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1

Finally we get

(Z(36)=>Z(36))*(Z(36)=>¬Z(8))*(Z(36)=>Z(2))*(Z(36)=>¬Z(1)) + (Z(36)=>A) = 1

what is not supposed to resolve problem like in sample 228
********************************************************************
See UPDATE as of 24/11/2018 in first rows of current post
********************************************************************

Thursday, November 8, 2018

Solution of problem type 23 from VK's News Wire 10.03.18 via technique developed in mea-2016-8.pdf

    Bellow we intend to benefit from idea of H.A, Mironchick building a graph
    for system of boolean equations using just one variable for establishing
    connection between equations in system on snapshot above.

   Perform substitute :-

     x1 ~ x3 = z1; x2 ~ x4 = z2; x5 ~ x7 = z3; x6 ~ x8 = z4; x9 ~ x10 = z5

Convert original system into

(z1 v z2)^(z1 => z2) = 0
(z2 v z3)^(z2 => z3) = 0
    (z3 v z4)^(z3 => z4) = 0
    (z4 v z5)^(z4 => z5) = 0
    (z1 => z2) => (z5 => z4) =1

    Build graph to solve system of first four equations

   (z1 => z2) =>(z5=> z4) = ( ¬z1 v z2) => (¬z5 v z4) =
   ¬(¬z1 v z2) v ( ¬z5 v z4) = z1^(¬z2) v ¬z5 v z4 = 1

Passing Polyakov's control

In other words we get 2^5 + 2^5 = 2^6 = 64 ( solutions for {x})

Straight forward mapping would look like

((x1~x3)v(x2~x4))^((x1~x3)=>(x2~x4)) = 0
((x2~x4)v(x5~x7))^((x2~x4)=>(x5~x7)) = 0
((x5~x7)v(x6~x8))^((x5~x7)=>(x6~x8)) = 0
((x6~x8)v(x9~x10))^((x6~x8)=>(x9~x10)) = 0
((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1

Build diagrama based on first equation which would work
for first four equations. Notice that transition pairs are x2x4 , x5x7 , x6x8

   In fact adding
         ((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1
   would add ( 0 => 0) => (0 =>0) =1 on lines "01" and "10"
   e.g. True => True = 1 . So adding this 5-th equation won't decrease number    of solutions of original sytem

   Thus answer is 64

Saturday, October 27, 2018

One more system of boolean equations solved via "Graphs and Systems of Logical equations" by E. A. Mironchick 08/2016

(x1=x2) v (x1=x3) v (x2=>x3) = 1
(x3=x4) v (x3=x5) v (x4=>x5) = 1
(x5=x6) v (x5=x7) v (x6=>x7) = 1
(x7=x8) v (x7=x9) v (x8=>x9) = 1
(x9=x10) v (x9=x11) v (x10=>x11) = 1

A diagram in rows and columns showing how the truth or falsity of a proposition varies with that of its components. (truth table for first equation)

Building graph and proceed with calculation :-

Passing control on Polyakov's Server

Another Sample

(x1=x2) v (x1=x3) v (x2⊕x3) =1
(x3=x4) v (x3=x5) v (x4⊕x5) =1
(x5=x6) v (x5=x7) v (x6⊕x7) =1
(x7=x8) v (x7=x9) v (x8⊕x9) =1
(x9=x10) v (x9=x11) v (x10⊕x11) =1

Truth table

Building graph

Passing control on Polyakov's Server

References

1. http://kpolyakov.spb.ru/download/mea-2016-8.pdf

Sunday, October 21, 2018

The most recent revision of non-linear case of task 18 in EGE Informatics vs Standard aproach to solve 18-th in EGE Mathematics

Consider problem 7 from recent presentation posted at
http://kpolyakov.spb.ru/school/ege.htm
Линейное (и нелинейное) программирование в задаче 18 ЕГЭ по информатике

Now detect A like we manage to get the job done
working on problems 18-th of EGE Mathematics

f1(x) =(x-A)^2 + 10
f2(x) = -x^2/4 + 30

System 1

(1) f1(x) = f2(x)
(2) df1(x)/dx= df2(x)/dx

Getting derivatives:-

df1(x)/dx = 2(x-A)
df2(x)/dx = -x/2

First:- Solve (2)

2(x-A) = -x/2
(5/2)x = 2*A
x = (4/5)*A

Second:- Solve (1)

((4/5)A -A)^2 + 10 = (-1/4)*(16/25)*A^2 + 30
(-1/5)^2*A^2 +10 = (-1/4)*(16/25)*A^2 + 30
((1/25)+(4/25))*A^2 = 20
(1/5)*A^2 = 20

Here we go :-

A^2 = 100
A= |100^(1/2)| = 10

Would I skip original declaration in header, new revision (non-linear) of 18 -th EGE Informatics would look pretty much like 18-th in EGE Mathematics having average level of difficulty.
Obviously complexity of non-linear revision of 18-th EGE Informatics might be significantly increased when it would be designed for real EGE exam.
1) Make skiils set to build area colored gray on second snapshot requiring
boolean algebra in depth knowledge.
2) Good background in differential geometry, specifically touch of curves related

Condition D=0 works only for parabolic curves. Method applied above has
universal nature. See for instance