2

Title is the question. This is from a timed competition

My strategy: 2020 in base 2 is 11111100100. Then, you can find the answer by $10 \cdot 9 + 9 \cdot 8 + 7...$. This gets me the answer 330, but it's not correct

  • What logic led you to $10\cdot 9 + 9\cdot 8 + \dots$? – JMoravitz Sep 10 '20 at 21:08
  • @JMoravitz I made the first digit fixed to 1, then there are 10 places for the second digit and 9 for the third digit. Then I made the second digit... –  Sep 10 '20 at 21:09
  • 1
    How can you tell the "second" digit apart from the "third"? Which one was in the middle versus which one was on the right? But then if you picked the second one and it was farther to the right than usual... did you really have $9$ options still for the third? – JMoravitz Sep 10 '20 at 21:10
  • @JMoravitz would this mean that there would be twice the amount? –  Sep 10 '20 at 21:10
  • 2
    Hint... every binary number less than or equal to $2047=2^{11}-1$ who has $3$ 1's in its representation will also be less than or equal to $2020$. This becomes then a question of how many ways you can choose $3$ of the eleven positions to be $1$'s while setting the rest of the positions as $0$'s. – JMoravitz Sep 10 '20 at 21:12
  • Yes, your answer was twice the intended amount, but you don't actually need to hardly do any arithmetic here at all... once understanding my hint, your answer can be expressed as a binomial coefficient. – JMoravitz Sep 10 '20 at 21:13
  • @JMoravitz so you are saying the answer is 11 choose 3? –  Sep 10 '20 at 21:14
  • 1
    Precisely. And if its a freeform answer style exam, an answer of $\binom{11}{3}$ is often preferable to an answer of $165$ unless explicitly stated that answers should be fully evaluated. – JMoravitz Sep 10 '20 at 21:16

1 Answers1

1

Because $2020$ is larger than $11100000000=1792$ in binary, any $3$ $1$s will suffice. There are $11$ digits, and you want only $3$ of them to be $1$s, and the rest are $0$s. Therefore, you can just do $_{11}C_3=165$.

KingLogic
  • 1,441
  • @chem1kal is this the right answer? – KingLogic Sep 10 '20 at 21:16
  • 1
    Yes, it is. You can also see @JMoravitz –  Sep 10 '20 at 21:19
  • 1
    Easily confirmable by running a simple python script followed by a grep. If the competition is on a command line system that's the fastest way almost. – Henno Brandsma Sep 10 '20 at 21:27
  • E.g.python -c 'for i in range(2020): print bin(i)[2:] ' | grep -c '^10*10*10*$' will do. – Henno Brandsma Sep 10 '20 at 21:31
  • @HennoBrandsma fastest if you think in code faster than you think in math. Someone well practiced in combinatorics could easily have the answer in a second or so... typing the grep command would likely take a few seconds at least even if you know what you're doing so I don't know that I'd call it faster. Of course, they say that one should plan the time limit for a test for students to take 5-10 times longer than it takes a teacher to solve it. – JMoravitz Sep 10 '20 at 21:32
  • @JMoravitz It could be a hacking competition instead of a maths one. I think for many people the script would be quicker to come up with. It depends on the audience. – Henno Brandsma Sep 10 '20 at 21:34