All integers from $1$ to one million are written on a tape in some arbitrary order. Then the tape is cut into pieces containing two consecutive digits each. Prove that these pieces contain all two-digit integers for sure, regardless of the initial order of integers.(4 points) Alexey Tolpygo
Problem
Source: Tournament of Towns Spring 2016
Tags: combinatorics
TheOneYouWant
22.02.2017 21:28
If $ab$ is the required two digit number, just find the number $ab0ab$ in the string, you're done...
dbz
28.04.2017 11:50
TheOneYouWant wrote: If $ab$ is the required two digit number, just find the number $ab0ab$ in the string, you're done... Can you please elaborate on your answer.I couldn't get it.
tarzanjunior
28.04.2017 13:03
dbz wrote: TheOneYouWant wrote: If $ab$ is the required two digit number, just find the number $ab0ab$ in the string, you're done... Can you please elaborate on your answer.I couldn't get it. Every number of the form $ab0ab$ is present since it is between 1 and 1 million.So search for that number. It can be cut like $ab$,$0a$,$ac$ where $c$ is also a digit. or $da$, $b0$,$ab$ where $d$ is a digit. Hence the string $ab$ is always present.
naenaendr
20.08.2019 03:31
Would this question also require that you show that there will exist pieces with numbers 01, 02, etc.? For that, you would just need the pigeonhole principle, but I'm not sure if it's needed to finalize the proof.