Brilliant Weekly Problems

January 1

Intermediate

Using an ordered alphabet of 26 letters, how many ways are there to chose a set of six different letters such that no two letters in the set are adjacent in the alphabet?

For instance, {ISOKAY} is a valid set of six letters, but {VETOIF} is not because E and F are both in the set.

Solution:

We can create a row of 27 boxes, the first empty and the rest filled with the letters A to Z in alphabetical order. We can then get 6 boxes of 2 with one filled and one empty, the filled one representing the letter we chose and the empty one to not chose any letter of the ones we have chosen before. We can see that we also need 15 other boxes to represent the non chosen letters not adjacent to the ones we chose. These boxes total to 6 + 15 = 21 and we must chose 6 or 15 of them. We get:

21*20*19*18*17*16 = 21*19*17*8 = 54264 ways.
6*5*4*3*2*1


Comments

  1. BunnyAugust 12, 2020 at 6:43 PM

    A very similar idea pops up in AMC contests too: https://strive4ww.blogspot.com/2020/08/choosing-subsets-without-consecutive.html

    ReplyDelete

Post a Comment

Popular posts from this blog

Math Formulas + Facts

Sum of cubes and Difference of Cubes a 3  + b 3  = (a + b) (a 2  − a b + b 2  ) a 3  - b 3  = (a - b) (a 2  + a b + b 2  ) Powers to know 5 7  = 78125 5 6  = 15625 5 5  = 3125 Compound Interest A = P(1+r/n) nt Harmonic Series 1+1/2+1/3+1/4+1/5+1/6...+1/n To estimate sum, take the 2 0  term for 1, then take the next 2 1  terms for 2, then take the next  2 2  terms for 3.... Sums: 2 - up to 1/4 2.5 - up to 1/7 3 - up to 1/11 3.5 - up to 1/19 4 - up to 1/31 4.5 - up to 1/51 5 - up to 1/83 Area of Octogon A = 2(1+√2) a 2 Finding the number sides of a regular polygon when you know the interior angle in degrees 180-x° = 360/n Finding total number of diagonals in a polygon n(n-3)/2
Read more

Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern: 9a \equiv 1 \pmod 7 \rightarrow a = 4 7b \equiv 1 \pmod 9 \rightarrow b = 4 Which is cool. But it continues: 7c \equiv 1 \pmod 5 \rightarrow c = 3 5d \equiv 1 \pmod 7 \rightarrow d = 3 And: 35e \equiv 1 \pmod 33 \rightarrow e = 17 33f \equiv 1 \pmod 35 \rightarrow f = 17 Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem: Theorem : The solutions a, b to the modular equivalences (n-1)a \equiv 1 \pmod {n+1} (n+1)b \equiv 1 \pmod {n-1} for positive even integers n satisfy a = b = \frac{n}{2}. Update  (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process. I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process ...
Read more

Cyclic Quattrocento (Fall 2021 AMC 12B #24)

Image
Fall 2021 AMC 12B #24 Problem:  Triangle ABC has side lengths AB = 11, BC=24, and CA = 20. The bisector of \angle{BAC} intersects \overline{BC} in point D, and intersects the circumcircle of \triangle{ABC} in point E \ne A. The circumcircle of \triangle{BED} intersects the line AB in points B and F \ne B. What is CF? Solution:  We can create a diagram to try to find unique relationships in this problem. By angle chasing in the cyclic quadrilateral ABEC given that AE is the angle bisector of \angle{BAC} we can find that \angle{BAE} = \angle{CAE} = \angle{BCE} = \angle{CBE}. This means that triangle BCE is isosceles and BE = CE, which may be useful later on. Now, we can focus on CF , which is the length we want to find. We can see that ACF has a cevian CB, so we can use Stewart's Theorem (we will "derive" it with the law of cosines here) to solve for CF in terms of other side lengths. We can let \angle{ABC} = \theta which means...
Read more