alt text

Counting Routes Problem

Let's count the number of routes from the bottom-left square to the top-right square

Solve this problem for both the 4x4 board and the 5x5 board

In [1]:
def routes(x,y):
    if x == 1: 
        return 1
    elif y == 1:
        return 1
    else:
        return routes(x-1,y)+routes(x,y-1)
In [2]:
routes(8,8)
Out[2]:
3432
In [3]:
for x in (5,4,3,2,1):
    print([routes(x, y) for y in [1,2,3,4,5]])
[1, 5, 15, 35, 70]
[1, 4, 10, 20, 35]
[1, 3, 6, 10, 15]
[1, 2, 3, 4, 5]
[1, 1, 1, 1, 1]

Let's look at the third row above, the row starting with [1,3,6,10,15].

What is the pattern? Is there a simple function that generates these numbers?

In [4]:
print([routes(x, 3) for x in [1,2,3,4,5,6,7,8,9,10]])
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
In [5]:
%%html
<script src="https://cdn.geogebra.org/apps/deployggb.js"></script>
In [6]:
%%html
<div id="ggb-point"></div>
<script>
  var ggbApp = new GGBApplet({
      "height": 400,
      "showToolBar": true,
      "showMenuBar": true,
      "showAlgebraInput": true,
      "showResetIcon": true,
      "enableLabelDrags": true,
      "enableRightClick": true,
      "enableShiftDragZoom": true,
      "useBrowserForJS": false,
      "filename": "files/GeogebraDemo.ggb"
  }, 'ggb-point');

  ggbApp.inject();
</script>

Let f(1)=1, f(2)=3, f(3)=6, f(4)=10, f(5)=15. What is the function f(x)?

In the above GeoGebra app, you found constants a, b, c for which f(x)=ax^2+bx+c. Let's test it out!

Can you explain WHY this formula is true?

In [16]:
def f(x):
    # replace the numbers 0.6, 0.7, 0.8 with the numbers a, b, c you found above
    return (0.6)*x*x + (0.7)* x + (0.8)

print([f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8)])
[2.0999999999999996, 4.6, 8.299999999999999, 13.2, 19.3, 26.599999999999998, 35.1, 44.8]

alt text