6
$\begingroup$

Moderator Note: This question is from a contest which ended 1 Dec 2012.

Consider Pascal's Triangle taken $\pmod 2$:

First few rows of Pascal's Triangle modulo 2

For simplicity, we will call a finite string of 0's and 1's proper if it occurs in one of the rows of this modified Pascal's triangle. (for example, 0 (row 3) and 10001 (row 5) are proper).

I've been exploring proper strings of length $n$. My professor told me it is possible to

i) characterize explicitly all proper strings of length $n$

and ii) Find an explicit formula for the number of proper strings of length $n$.

But I cannot figure out how to even begin either parts. This is a very interesting problem, and I was wondering if someone could help me. Thank you!

  • 1
    @Andy I suggest that you tell us in which context your professor told you all this. For this problem, I suggest that you gives us all the strings of length $\le 10$ that you could not find.2012-11-05

2 Answers 2

1

(The following was shown to me a few years ago by David Kelly, who used this discovery to generate an approximation of the Sierpinski Triangle by looking at Pascal's Triangle in base 2 -- though the details of this part escape me.)

Let $n \in \mathbb{N}$, and let:

$F(n) = \textrm{max}\{k \in \mathbb{N} \, \colon \, 2^k \textrm{ divides }n\}.$

$B(n) = \textrm{ count of 1s in the base-2 representation of } n.$

$P(n) = \textrm{ count of odd numbers in the } n\textrm{th row of Pascal's Triangle.}$

Proposition: For every $n \in \mathbb{N}$, the following hold:

  1. $F(n) + B(n) = n,$
  2. $P(n) = 2^{B(n)}.$
  • 0
    Well, the values for B(n) and P(n) are obtained by string operations.2012-11-05
0

You start by drawing a very large example of the triangle. Or finding it somewhere on the internet. Then start looking for regularities. Patterns that occur.

(edit). My initial ideas. You can see long runs of $1$'s or long runs of $0$'s. I can see $0110$, by I think I cannot find $01110$. Why? What can be above that sequence...

  • 0
    That much I figured :) But patterns only yield so much insight.... and for me, none at all :P2012-11-05