jagan028's blog

Help me find proof behind pattern — CF div3 round 1006 Problem F
By jagan028, 5 hours ago, In English

Problem: 2072F - Goodbye, Banker Life

I learned about the Pascal's triangle solution, but i upsolved it by seeing this pattern:

1

1 1

1 0 1

1 1 1 1

Exact pattern

It recursively repeats..

Solution

Thing is, I'm unable to prove why this should work and its bothering me alot, can anyone help me out?!

Update : The pattern is known as sierpinski's triangle

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

you can think in pascal triangle for cell (i , j) how many times the cell (1 , 1) contribute at so like

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

for example so Now known the fact that the cell (i , j) of pascal triangle is Ncr(i , j) and knowing also that in pascal triangle the value of the cell(i , j) is how many time the root (cell(1 , 1)) effect on the cell (i , j) , we can know that Ncr(i , j) is equal to the number of times the root contribute to cell (i , j) returning to our problem which change the operator in pascal triangle to XOR , to solve we just need to know the parity for the contribution from the root to the cell we need , so we just interested in parity of (Ncr(n , i)).

to solve the previous subproblem there are two ways 1. use Locus theorem that mention to know that if Ncr(i , j) is odd then No bit equal to 1 in j that is a 0 in i 2. you can just keep tracking of number of two in factorials and to know the Ncr(i , j) is even number of twos in fact[i] > number of twos in fact[j] + number of twos in fact[i — j]

→ Reply
  • »
    »
    5 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, i got the pascal's triangle solution, I was talking about a recursive solution where a basic pattern kept repeating itself!

    Sorry, I added it under spoiler tag by mistake, corrected it now

    → Reply
»
5 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Think of xor as binary addition without carrying. Then the xor of the two elements above the current element is just the sum of the two elements above in binary without carrying.

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm stuck... how can I use that to prove the pattern I mentioned?

    → Reply
    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Oh mb I thought you were asking why Pascal's triangle is relevant... I don't know why it appears either, but the pattern is called Sierpinski's triangle if you want to look it up.

      → Reply
      • »
        »
        »
        »
        5 hours ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        It was my bad, i initially had it under spoiler tag.. thanks tho, I'll look it up!

        → Reply
»
5 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Legendre’s theorem combined with factorial definition of combinations works

→ Reply
»
95 minutes ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

By Lucas's Theorem or Kummer's Theorem, $$$\binom{a+b}a$$$ is odd if and only if $$$a$$$ and $$$b$$$ do not share any ones in their binary representations. Therefore, Sierpinski's Triangle comes from $$$\binom{i+j}i$$$ being odd if and only if $$$\binom{2^k+i+j}{2^k+i}$$$ is odd, if and only if $$$\binom{2^k+i+j}i$$$ is odd whenever $$$2^k>i,j$$$, since you can visualize this as recursively constructing the triangle given the first $$$2^k$$$ rows by sliding it $$$2^k$$$ down and then copying it on the left and right side to form the next $$$2^k$$$ rows.

→ Reply