none
Maths Challenge 2 - October 2013 RRS feed

  • Question

  • Tried Maths Challenge 2 from Challenge of the Month - October 2013:

    I have 12 steps, and I can go down them in steps of 1 or 2.  How many different ways could I go down the steps.  For example I could take 12 single steps (1-1-1-1-1-1-1-1-1-1-1-1) , 6 double steps (2-2-2-2-2-2), 1-2-2-1-2-1-1-2 or any other combination.


    But when i read it the 2nd time i realized, that my 'solution' of 63 is completely wrong, because
    lines 2 to 6 contain additional/multiple combinations (something with nCr, nPr like picking 1 or 2 balls out of a bag containing 12 balls and count these pickings)

    So, to achieve the correct sum of all possible combinations, it would be neccessary (lines 2-6) to swap always the most right blue brick with its right yellow neighbour brick until the end of the line, then next (left) blue brick aso, until all blue bricks are ordered on the right side (and all yellow ones left). And additionally count/add every move.

    Nevertheless i got totally confused and stucked when it comes to fill the remaining white fields with yellow bricks, down at
    'FillUp()               ' NOT WORKING yellow bricks to fill up the rest

    Stairway.zip  (Bricks included)
    Maybe anyone has an idea.


    Monday, October 28, 2013 10:37 PM
    Answerer

Answers

  • See Nonki's answer (correct 233).

    Basically if we take only single steps they are all 1s and there is 1 way we can do this.

    If we take one double, there are 10 singles (11 in all) we can choose this in 11 ways

    If we take 2 doubles, there are 8 singles (10 in all) we can do this in 45 ways 10!/2!/8!

    etc

    This is a rather tough problem, but one given to my kids at school (they didn't get it right).


    Tuesday, October 29, 2013 6:45 PM
    Moderator

All replies

  • See Nonki's answer (correct 233).

    Basically if we take only single steps they are all 1s and there is 1 way we can do this.

    If we take one double, there are 10 singles (11 in all) we can choose this in 11 ways

    If we take 2 doubles, there are 8 singles (10 in all) we can do this in 45 ways 10!/2!/8!

    etc

    This is a rather tough problem, but one given to my kids at school (they didn't get it right).


    Tuesday, October 29, 2013 6:45 PM
    Moderator
  • Yep, i think they did it when they worked about power of binoms (a+b)^n and it comes to binominalcoefficient (n over r, or nCr).

    12 over 12    12!/(12-12)!/12!     1          only 1er
    11 over 10    11!/(11-10)!/10!    11         1 double
    10 over  8    10!/(10-8)!/8!         45         2  -"-
     9 over  6     9!/(9-6)!/6!            84          3 double
     8 over  4     8!/(8-4)!/4!           70           4 double
     7 over  2     7!/(7-2)!/2!           21            5 double
     6 over  6     6!/(6-6)!/6!            1             6 double
    ------------------------------------   233

    NaochanON's right. Also took his pure output, let it sort and scan for duplicate lines -> none -> right! (only 1er and 2er)

    CombPermutCalc

    Order important?    NO
    Repetition        NO

    Upper example would look nice with swap animations etc. but much too complicated. Remember a swap demo from you (about parallel proc) with little shapes, but running that in multiple loop calculations would be a year's challenge for me.

    Tuesday, October 29, 2013 8:30 PM
    Answerer