Given an integer N. Count all pairs of integers from 0<=x,y<2^N , such that OR(x,y) = XOR(x,y).

By running bruteforce, I found out that the answer is 3^N, but I have no proof of my solution. Can someone help with the proof?

Because for every n spaces, there are 3 options

00,01,10 because in case of 11 or and xor is different. So, 3^n.

2**N means there are N bits. If you see the above conditions is only possible in these -

0 1

1 0

0 0

so for each N bit we have three options

You can think like you need to count the pairs where the and of them is zero.

As if xor(x,y) == or(x,y)

It means in their binary representation

0^0 = 0 , 0|0 = 0

1^0 = 1 , 1|0 = 1

0^1 = 1 , 0|1 = 1

1^1 = 0 , 1|1 = 1

Now we can say if x&y is not equal to zero then at some position we have set bits in x and y, and hence if we have set bits at a position in both the nos. then their xor and or won’t be equal. So we need to find out the pairs where the x&y == 0 to get the answer for xor(x,y) == or(x,y).

If someone’s looking for a more rigorous proof,

So let’s make a few important observations first (which I’m pretty sure that you might have noticed already) :

1. If x=1 then the value of y is bound to be 0 (\because 1\oplus0=1|0, 1\oplus1\neq1|1))

2. If x=0 then the value of y can be 0 or 1.

Now firstly we will try to fix our x and then find all the y's which satisfy this equation. For example, let our x has the binary representation as follows x=11001.

So from observation (1) we can say that all the bits which are set in x will be unset in y. Hence in this case y will be of the form y=00--0.

From observation (2) we can say that for each unset bit in x we have 2 options i.e. we can either have the corresponding bits in y as 0 or 1.

So for any x if the number of unset bits in x is u(x) then number of y's will be 2^{u(x)}.

Hence final S=\sum_{i=0}^{2^N}2^{u(i)} where u(i) is the number of unset bits in i.

Now if we use the contribution technique for each 1\le u \le N then each 2^u we will have a contribution of \binom{N}{u} (since we can have any u bits out of N as unset) i.e.

S=\sum_{u=0}^{N}\binom{N}{u}2^{u} \implies S=(1+2)^N=3^N

Thank you guys🙌