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 )



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

######################
UPDATE  as of 05/12/2018
######################

Following lines must  be removed from blog
due to explanation provided by Helen Mironchick which
allowed me start to understand her original idea properly.


# In particular case for any (n: n mod 2 = 0)  E(n+1) = E(n) + E(1) ,
# what actually seems to be enough to reproduce a bunch of samples
# kind of printed above as well as in original manuscript
# However, E(36) != E(35) + E(1) so we are getting obvious restriction
# for method ( approach )

New face of Google translator


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

8 comments:

  1. Вы пишете: "Однако E (36)! = E (35) + E (1), поэтому мы получаем очевидное ограничение для метода (подхода)" ссылаясь на статью Мирончик Е.А. Но там этого нет! Там введен термин "базисный предикат" и идет разложение на базисные предикаты (индексы степени 2).

    ReplyDelete
    Replies
    1. Елена ! Я согласен там этого нет.Фраза не точна.
      Я хотел сказать только что :-
      Define Betta(n) to be the set of "1-th orded as they should stand in binary presentation of n" then
      E(n+m)=E(n)+E(m) if and only if Betta(n) ∩ Betta(m) = ∅
      вне связи с Вашей статьей. Извините.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Выражения типа x & 5 = 4 также представимы в виде базисных предикатов. В битовом представлении числа х имеется единица на второй позиции (Е4) и отсутствует единица на нулевой позиции. Что соответствует записи:
    E4 И НЕ (E1)

    ReplyDelete
    Replies
    1. Bitwise2 expression :-
      (x&5 = 4) = Z(1)*!Z(4)
      Ваша работа (как мне кажется сейчас) двойственна технологии Bitwise2 в силу определения E(k) у Вас и Z(k) в Bitwise2.

      Delete
  4. Думаю,что например E(4)+!E(1) <=> Z(1)*!Z(4)

    ReplyDelete
  5. Если честно, я не читаю английский, а с переводчиком получается непонятно. В методе описанном К.Ю. (по Здвиженковой) идет сведение к импликации и много частных случаев и фразы "согласно правилу №13"... Мне мой метод кажется интереснее (не настаиваю) т.к. нет никаких особых случаев. Есть только "основной набор" законов логики. И дополняя его (не обязательно, но детям понятнее) кругами и штриховкой описанных множеств, решение очень простое.

    ReplyDelete
  6. Если честно,то я никогда не работал в школе, a на мехмате "Дискретку" сдап и забыл.К.ф.м.н. - многомерный комклексный анализ (1984). Описание сопряженных к пространствам аналитических функций с заданным ростом вблизи границы в терминах Фурье-Лапласа. Тривиальность групп когомологий с оценками в когеррентных аналитических пучках (теория Ока-Картана). Есть статья в ДАН - основной результат и еще 5-6 в центральной печати. Мне нравятся работы К.Ю.,как математику,и Ваши - Метод Отображений 2013/2016 (просто великолепно).Возможно,Вам будут интересны посты на
    https://vk.com/bderzhavets (как "Метод Отображений vs Метод битовых масок (once again). Нетривиальные возможности метода отображений (Графики и системы булевых уравнений по Е.А.Мирончик 08/2016")). С уважением. Борис.

    ReplyDelete