|
|
| Line 1: |
Line 1: |
| | == Problem == | | == Problem == |
| − | What is the minimum number of successive swaps of adjacent letters in the string <math>ABCDEF</math> that are needed to change the string to <math>FEDCBA?</math> (For example, <math>3</math> swaps are required to change <math>ABC</math> to <math>CBA;</math> one such sequence of swaps is
| + | How many ordered pairs <math>(m, n)</math> of positive integers exist such that <math>m</math> is a factor of <math>54</math> and <math>mn</math> is a factor of <math>70</math>? |
| − | <math>ABC\to BAC\to BCA\to CBA.</math>) | |
| | | | |
| − | <math>\textbf{(A)}~6\qquad\textbf{(B)}~10\qquad\textbf{(C)}~12\qquad\textbf{(D)}~15\qquad\textbf{(E)}~24</math> | + | <math>\textbf{(A)}~2 \qquad\textbf{(B)}~4 \qquad\textbf{(C)}~10 \qquad\textbf{(D)}~12 \qquad\textbf{(E)}~16</math> |
| | | | |
| − | == Solution 1 (Analysis) == | + | ==Solution== |
| − | Procedurally, it takes:
| + | The greatest common divisor of <math>54</math> and <math>70</math> is <math>2</math>, so we know that <math>m</math> is either <math>1</math> or <math>2</math>. If <math>m = 1</math>, then <math>n</math> can be any factor of <math>70</math>, so <math>8</math> options. If <math>m=2</math>, <math>n</math> can be any factor of <math>35</math>, so <math>4</math> options. In total, there are <math>\boxed{\textbf{(D)}~12}</math> ordered pairs. |
| | | | |
| − | * <math>5</math> swaps for <math>A</math> to move to the sixth spot, giving <math>BCDEFA.</math>
| + | ~joshualiu315 |
| − | | |
| − | * <math>4</math> swaps for <math>B</math> to move to the fifth spot, giving <math>CDEFBA.</math>
| |
| − | | |
| − | * <math>3</math> swaps for <math>C</math> to move to the fourth spot, giving <math>DEFCBA.</math>
| |
| − | | |
| − | * <math>2</math> swaps for <math>D</math> to move to the third spot, giving <math>EFDCBA.</math>
| |
| − | | |
| − | * <math>1</math> swap for <math>E</math> to move to the second spot (so <math>F</math> becomes the first spot), giving <math>FEDCBA.</math>
| |
| − | | |
| − | Together, the answer is <math>5+4+3+2+1=\boxed{\textbf{(D)}~15}.</math>
| |
| − | | |
| − | ~MRENTHUSIASM
| |
| − | | |
| − | == Solution 2 (Recursive Approach)==
| |
| − | | |
| − | We can proceed by a recursive tactic on the number of letters in the string.
| |
| − | | |
| − | Looking at the string <math>A</math>, there are <math>0</math> moves needed to change it to the string <math>A</math>
| |
| − | | |
| − | Then, there is <math>1</math> move to change <math>AB</math> to <math>BA</math>.
| |
| − | | |
| − | Similarly, there is <math>3</math> moves needed for three letters (said in the problem).
| |
| − | | |
| − | There are <math>6</math> moves needed to change <math>ABCD</math> to <math>DCBA</math>.
| |
| − | | |
| − | We see a pattern of <math>0,1,3,6,...</math>. We notice that the difference between consecutive terms is increasing by <math>1</math>, so in the same way, for <math>5</math> letters, we would need <math>10</math> moves, and for <math>6</math>, we would need <math>\boxed{\textbf{(D)}~15}</math> moves.
| |
| − | | |
| − | Thinking why, when we start making these moves, we see that for a string of length <math>n</math>, it takes <math>n-1</math> moves to move the last letter to the front. After, we get a string that will be changed identically to a string of length <math>n-1</math>. This works in our pattern above and is another way to think about the problem!
| |
| − | | |
| − | ~world123
| |
| − | | |
| − | Note:
| |
| − | | |
| − | The sequence consists of triangular numbers shifted a term up (as it starts with <math>0</math> on term <math>1</math> and <math>1</math> on term <math>2</math>.)
| |
| − | Thus, our explicit formula is <cmath>\dfrac{(n-1)(n+1-1)}{2} = \dfrac{(n)(n-1)}{2}</cmath> and as <math>n = 6</math> in this case (<math>6</math> letters), our answer is <math>\dfrac{(6)(6-1)}{2} = \boxed{\textbf{(D)}~15}</math>
| |
| − | | |
| − | ~NSAoPS
| |
| − | | |
| − | == Solution 3 (Solution 2 Done Fast)==
| |
| − | | |
| − | We can see that the most efficient way to change <math>ABCDEF</math> to <math>FEDCBA</math> is the same as changing <math>ABCDE</math> to <math>EDCBA</math> and then moving <math>F</math> to the front in <math>5</math> moves. Similarly, this would carry on downwards, where to change <math>ABCDE</math> to <math>EDCBA</math> would be to change <math>ABCD</math> to <math>DCBA</math> and move <math>E</math> <math>4</math> times to the front. This pattern will carry on until <math>AB</math> to <math>BA</math> would be <math>1</math>, and <math>A</math> to <math>A</math> would be <math>0</math>. The answer would be <math>0(A)+1(B)+2(C)+3(D)+4(E)+5(F)</math>, which is <math>\boxed{\textbf{(D)}~15}</math> moves.
| |
| − | | |
| − | ~Moonwatcher22
| |
| − | | |
| − | == Solution 4 (If you don't notice anything)==
| |
| − | Simply, just blindly doing it, the most straightforward way is to shift F all the way back. From ABCDEF:
| |
| − | | |
| − | <math>ABCDFE ->ABCFDE ->ABFCDE ->AFBCDE ->FABCDE</math>
| |
| − | | |
| − | For E:
| |
| − | | |
| − | <math>FABCED -> FABECD -> FAEBCD -> FEABCD</math>
| |
| − | | |
| − | For D:
| |
| − | | |
| − | <math>FEABDC -> FEADBC -> FEDABC</math>
| |
| − | | |
| − | For C:
| |
| − | | |
| − | <math>FEDACB -> FEDCAB</math>
| |
| − | | |
| − | For B:
| |
| − | | |
| − | FEDCBA
| |
| − | | |
| − | That's it, you don't need to do it with A. Still <math>\boxed{\textbf{(D)}~15}</math> moves.
| |
| − | | |
| − | ~pepper2831
| |
| − | | |
| − | ==Solution 5 (Inversions of Permutations)==
| |
| − | | |
| − | Let the letters <math>A, B, C, D, E, F</math> correspond to the numbers <math>1, 2, 3, 4, 5, 6</math> respectively. We want to find the number of swaps required to transform the permutation <math>1 2 3 4 5 6</math> into the permutation <math>6 5 4 3 2 1</math>.
| |
| − | | |
| − | Here, we let <math>1 2 3 4 5 6</math> be the natural order. Then the total number of inversions of the permutation <math>6 5 4 3 2 1</math> is <math>1+2+3+4+5=15</math>. Hence the answer is <math>\boxed{\textbf{(D)}~15}</math>
| |
| − | | |
| − | ~tsun26
| |
| − | | |
| − | == Video Solution by Pi Academy ==
| |
| − | https://youtu.be/6qYaJsgqkbs?si=K2Ebwqg-Ro8Yqoiv
| |
| − | | |
| − | == Video Solution 1 by Power Solve ==
| |
| − | https://youtu.be/j-37jvqzhrg?si=ieBRx0-CUihcKttE&t=616
| |
| − | | |
| − | == Video Solution by Daily Dose of Math ==
| |
| − | | |
| − | https://youtu.be/-EFTk2pBFug
| |
| − | | |
| − | ~Thesmartgreekmathdude
| |
| − | | |
| − | ==Video Solution by SpreadTheMathLove==
| |
| − | https://www.youtube.com/watch?v=_o5zagJVe1U
| |
| − | | |
| − | ==Video Solution by Just Math⚡==
| |
| − | https://youtu.be/KrkjGpk1uZs
| |
| | | | |
| | ==See also== | | ==See also== |
| | {{AMC10 box|year=2024|ab=A|num-b=5|num-a=7}} | | {{AMC10 box|year=2024|ab=A|num-b=5|num-a=7}} |
| | {{MAA Notice}} | | {{MAA Notice}} |
of positive integers exist such that 
is a factor of 
and 
is a factor of 
?
, so we know that 
or 
, then 
can be any factor of 
options. If 
, 
, so 
options. In total, there are 
ordered pairs.
