Solution of one system of equations in boolean variables via bitmasks in regards of training for Unified State Examination in Informatics (Russia)

In brief, bitmasks are supposed to be a core tool for solution of systems of equations in Boolean variables versus method suggested at
https://inf-ege.sdamgia.ru/test?theme=264
for task 11 which is pretty much similar to sample been analyzed bellow

*************************************
Original task looks like :-
*************************************
Determine total number of corteges
{x1,…,x9,y1,….,y9} which and only which
satisfy system :-

((x1 ≡ y1) → (x2 ≡ y2)) ∧ (x1 → x2) ∧ (y1 → y2) = 1
((x2 ≡ y2) → (x3 ≡ y3)) ∧ (x2 → x3) ∧ (y2 → y3) = 1

((x8 ≡ y8) → (x9 ≡ y9)) ∧ (x8 → x9) ∧ (y8 → y9) = 1

Consider truncated system :-

(x1 → x2) ∧ (y1 → y2) = 1
(x2 → x3) ∧ (y2 → y3) = 1

(x8 → x9) ∧ (y8 → y9) = 1

Now build well known bitmasks for {x} and {y}

x1 x2 x3 x4 x5 x6 x7 x8 x9
—————————————-
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1
0   0   0   1   1   1   1   1   1
0   0   0   0   1   1   1   1   1
0   0   0   0   0   1   1   1   1
0   0   0   0   0   0   1   1   1
0   0   0   0   0   0   0   1   1
0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0

y1 y2 y3 y4 y5 y6 y7 y8 y9
—————————————–
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1
0   0   0   1   1   1   1   1   1
0   0   0   0   1   1   1   1   1
0   0   0   0   0   1   1   1   1
0   0   0   0   0   0   1   1   1
0   0   0   0   0   0   0   1   1
0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0

We would name bellow first matrix “X” an second “Y”

For j=2 to j=9 consider  following two concatenations
“X” ->”Y” and “Y” -> “X”

First one :-

X                                     Y
---------------------------           ------------------------------
|                         |           |                            |
---------------------------           ------------------------------ 
j                         |           |                            |   
---------------------------           ------------------------------ 
. . . .                   |           j+1                          | 
---------------------------           ------------------------------
                                      j+2                          |
                                      ------------------------------        
                                      | . . . . .                  |
---------------------------           ------------------------------  
10                        |           10                           |     
---------------------------           ------------------------------ 
                                      

Record {j} from X with records {j+1,j+2,. . . 10} from Y
and vice versa second one :-

Y                                     X
---------------------------           ------------------------------
|                         |           |                            |
---------------------------           ------------------------------ 
j                         |           |                            |   
---------------------------           ------------------------------ 
. . . .                   |           j+1                          | 
---------------------------           ------------------------------
                                      j+2                          |
                                      ------------------------------        
                                      | . . . . .                  |
---------------------------           ------------------------------  
10                        |           10                           |     
---------------------------           ------------------------------

Record { j } from Y with records {j+1,j+2,. . . 10} from X

We’ll get total 2*(10-j) сorteges making boolean value of implication

((x[j-1] ≡ y[j-1])) → (x[j] ≡ y[j]) equal FALSE

**************************************
For instance when j=3 we get
**************************************

x1 x2 x3 x4 x5 x6 x7 x8 x9
—————————————-
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1   =>
0   0   0   1   1   1   1   1   1
0   0   0   0   1   1   1   1   1
0   0   0   0   0   1   1   1   1
0   0   0   0   0   0   1   1   1
0   0   0   0   0   0   0   1   1
0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0

y1 y2 y3 y4 y5 y6 y7 y8 y9
—————————————–
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1
0   0   0   1   1   1   1   1   1 <=
0   0   0   0   1   1   1   1   1 <=
0   0   0   0   0   1   1   1   1 <=
0   0   0   0   0   0   1   1   1 <=
0   0   0   0   0   0   0   1   1 <=
0   0   0   0   0   0   0   0   1 <=
0   0   0   0   0   0   0   0   0 <=

Vice Versa Set :-

y1 y2 y3 y4 y5 y6 y7 y8 y9
—————————————–
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1 =>
0   0   0   1   1   1   1   1   1
0   0   0   0   1   1   1   1   1
0   0   0   0   0   1   1   1   1
0   0   0   0   0   0   1   1   1
0   0   0   0   0   0   0   1   1
0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0

x1 x2 x3 x4 x5 x6 x7 x8 x9
—————————————-
1   1   1   1   1   1   1   1   1
0   1   1   1   1   1   1   1   1
0   0   1   1   1   1   1   1   1
0   0   0   1   1   1   1   1   1 <=
0   0   0   0   1   1   1   1   1 <=
0   0   0   0   0   1   1   1   1 <=
0   0   0   0   0   0   1   1   1 <=
0   0   0   0   0   0   0   1   1 <= 
0   0   0   0   0   0   0   0   1 <=
0   0   0   0   0   0   0   0   0 <=

****************************************************************************
So when j=3 we have 2*7 = 14 corteges where x2≡y2 is True
and x3≡y3 is False. So,  (x2 ≡ y2) → (x3 ≡ y3) is actually 1 -> 0
what is False by definition.
****************************************************************************

What is sign that set of corteges generated for each j from [2.3.4,…,9]
should be removed from 100 total solutions of truncated system of boolean
equations.

Now calculate :-

s:= 0 ;
for j=2 to j=10 do
begin
s:= s + (10-j) ;
end ;
s= 2*s ;
writeln (s);

Finally, we get s=72

Total number of corteges obtained via decart multiplication of X and Y is equal 100. So number of solutions of original system would be 100-72=28

I appreciate courtesy provided by informatik “BU”
https://www.youtube.com/watch?v=MDL5Mym5Aac
However, don’t behave so nicely as “BU” always does.

3 Responses to Solution of one system of equations in boolean variables via bitmasks in regards of training for Unified State Examination in Informatics (Russia)

  1. Greetings! This is my 1st comment here so I just wanted to give a quick shout out and say I genuinely
    enjoy reading through your articles. Can you suggest any
    other blogs/websites/forums that cover the same
    subjects? Thank you so much!

  2. dbaxps says:

    Unfortunately all manuals written by EGE developers and myself were done in russian . I did a couple in English just because of offensive content. To hide it from some categories of readers.
    Here is my core blog clearly demonstrating power of Mapping method by Helen Mironchick. Same task may be solved via mentioned method in a few minutes. Fell free to see
    https://informatics-ege.blogspot.com/ and my page on VK
    https://vk.com/bderzhavets .
    Thanks a lot for your feedback.
    Boris

  3. dbaxps says:

    I pointed to my sources only because you would be able to find stuff been written in English. Would you understand Russian Please,see original work belongs to Helen
    http://kpolyakov.spb.ru/download/mea-2013-10.pdf
    http://kpolyakov.spb.ru/download/mea-2016-8.pdf
    http://kpolyakov.spb.ru/download/mea18bit.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: