Maths Olympiad Prep

Library / /6 of 23

Combinatorics Difficulty 5.4 AIME, harder Prove it Romania

On a blackboard there are written, one after another, all positive integers from 11 to 3000030000, forming the following sequence of digits:
12345678910111230000123456789101112\ldots30000.
Find the number of occurrences of 20232023 in this sequence.

Solution

The sequence 20232023 appears 1313 times in the writing of 20232023, 1202312023, 2202322023 and of 2023020230, 2023120231, 2023220232, \ldots, 2023920239. Moreover, 20232023 can appear by connecting the end of a number to the beginning of the next number. The writing 2023202|3

appears only once, in 320232033202|3203, and the writing 202320|23 appears 1111 times, in 232023212320|2321 and from 230202302123020|23021 to 239202392123920|23921. The writing 20232|023 is impossible, because no positive integer begins with 00, therefore the number of occurrences of 20232023 is 13+11+1=2513 + 11 + 1 = 25.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.