2

Two circles of different radii are cut out of cardboard. Each circle is subdivided into $200$ equal sectors. On each circle $100$ sectors are painted white and the other $100$ are painted black. The smaller circle is then placed on top of the larger circle, so that their centers coincide. Show that one can rotate the small circle so that the sectors on the two circles line up and at least $100$ sectors on the small circle lie over sectors of the same color on the big circle.

I know at least three solution (pigeon hole, probabilistic and some double counting, they are basicly the same, see:

of this problem and now I'm intersted if someone has idea how to finish this one:

So we can think this $200$ sectors as vectors $u$ and $v$ in $\mathbb{Z}^{200}$ with entries $100$ times $-1$ (for black) and $100$ times $1$ (for white). Now there is a shift operator $R$ which moves all entries of vector for one place to the right, so we can think every power $R^k$, $k\in \{0,1,2,...,199\}$ as some rotation. Now we have to prove there is such $k$ that standard $$\langle R^kv,u\rangle \; \geq\; 0$$

Any idea how to achieve that?

This operator in $\mathbb{Z}^{4}$ is like: $$R =\pmatrix{0&0&0&1\\ 1&0&0&0\\0&1&0&0\\ 0&0&1&0\\ } $$

nonuser
  • 90,026

2 Answers2

1

Eh, I think I found the way out my self.

Say we have for each $k$: $$\langle R^kv,u\rangle \; <\; 0$$ Then $$ \langle\sum _{k=0}^{199} R^kv,u\rangle = \sum _{k=0}^{199} \langle R^kv,u\rangle \;<\; 0$$

But $\sum _{k=0}^{199} R^k =E$ where $E$ is a matrix with all entries $1$, so $$\sum _{k=0}^{199} R^kv = Ev = {\bf 0}= (0,0,0,....,0)$$ So we have $$ 0=\langle Ev,u\rangle =\langle\sum _{k=0}^{199} R^kv,u\rangle \;<\; 0$$ A contradiction.

nonuser
  • 90,026
  • Right, which is essentially the PGP argument (as in it doesn't require any special facts about vectorspaces) – Calvin Lin Jun 26 '20 at 14:26
  • Yes, unfortenutely. @CalvinLin – nonuser Jun 26 '20 at 14:28
  • Any way, it seems that is wrong, since I never used there is 100 white and 100 black sectors on a big circle. @CalvinLin – nonuser Jun 26 '20 at 14:32
  • You did, in $Ev = 0$. $v$ is the vector representing the big circle, and has 100 +1, 100 -1's. (Recall that E isn't the 0 matrix, but the all 1's matrix) – Calvin Lin Jun 26 '20 at 14:43
  • No, big circle is $u$. – nonuser Jun 26 '20 at 14:46
  • 1
    Oh true. In fact, what you proved is that the answer is independent of how the big circle is shaded! Nice result. (This also follows from the PGH counting argument). I think that furthermore (but haven't thought through fully, need to rush off), if the small circle is shaded with ${ 100-a, 100 + a }$ sectors and the big circle is shaded with $ { 100-b, 100 + b } $ sectors, then we can match at least $\min (100 + a, 100 + b)$ sectors. – Calvin Lin Jun 26 '20 at 14:58
0

Consider rotating the top disk to all $200$ positions, counting the matching sectors at each position, and adding the results. Each of $200$ sectors will match in $100$ positions, so the total is $20000$. If the number of matches is less than $100$ in all $200$ positions, the total will be less than $20000$, so at least one sector will have at least $100$ matches.

Ross Millikan
  • 374,822