DEV Community: Samuel Kendrick

A math game called 0-20

Samuel Kendrick — Wed, 09 Oct 2024 11:16:52 +0000

I take my 4 year old to a math circle at a nearby university. If you don't know what a math circle is, check this out: https://www.cut-the-knot.org/books/Reviews/BerkeleyMC1.shtml.

Math circles are weekly math programs that attract middle and high school students to mathematics by exposing them to intriguing and intellectually stimulating topics, rarely encountered in classrooms.

Maybe a good summary is that it's a program design to present children with fun, failure, and puzzles. All in the aim of distinguishing mathematics from merely arithmetic or doing things computers do, but by hand.

Anyways, our circles begin with a game. It looks like this:

Make a straight line of 21 paper plates on the floor.
Next, label the plates beginning with 0 and ending with 20.
Select two players.
Determine who goes first.

Now, before I explain a few more instructions, I'll make a board.

The two players alternate choosing how many steps to take together. In other words, the two players move together. The objective of each player is to be the one responsible for landing each other on plate 20. Finally, the last instruction is that you can only choose to move 1, 2, 3, or 4 steps at a time.

Like all games, this will be easier to grok after watching it. In fact, I'm shocked that my 4 year old ever understood this game.

To demonstrate, I'll show you exactly what my son did when playing the game for the first time. Keep in mind that this game rewards courtesy (more on that later). Below is a faithful reproduction of his first game. The names have been changed to protect identity.

Players: Dr. S, PhD & Daniel

Dr. S : Would you like to go first or second?
Daniel: First.
Dr. S : Ok, how many steps should we take? 1,2,3, or 4?
Daniel: 4.
Dr. S : Ok.

(Now it becomes obvious that Daniel has selected 4 because it provides him with the biggest number of plates to jump. He jumps, somewhat impressively, from 0 to 4. Dr. S says that he doesn't think he's that good at jumping, so he takes four steps.)

Dr. S : Now it's my turn to choose. I'll choose to go 1 step.

(Now they're at plate #5.)

Dr. S : Alright, how many steps should we take?
Daniel: 4.

(He jumps again and they make it to #9.)

Dr S : I'll take 1 step again.

(They arrive on plate #10.)

Dr S : How many steps?
Daniel: 4.

(At this point a couple of the brighter children realize that Daniel has picked a losing strategy. He doesn't notice them, blinded by the radiance of his long jumping ego. They arrive at plate #14.)

Dr S : How many steps do you think I'll take?
Daniel: 1.
Dr S :Yep.

(They arrive at plate #15.)

Daniel: 4 steps.

(They arrive at p late #19.)

Dr S : I'll take my one step. I win. Thanks for playing, Daniel.

(They exchange a high five and Daniel walks back to me, proud of his jumping.)

Here's a sequence of their steps: 0, 4, 5, 9, 10, 14, 15, 19, 20. As mentioned previously, this game rewards courtesy, not impressive hops. Dr. S won the game by going second and by knowing where to go. So long as you know what you're doing, you cannot lose the game if you go second.

I wanted my son to grok this game. I took a piece of paper and drew 20 squares on it, labelled 1-20. Then we played the game with two little people toys. We played a round and he was mildly interested in it. To get some skin in the game, I placed a mini marshmallow on square 20. After that, he was motivated. Unfortunately, I had to win three games in a row. His eyes were a bit watery, so I encouraged him that he could beat me once he understands the game.

To facilitate this eureka moment, I drew another board. This time it was with numbers from 0-5. Instead of a square, I drew a star around spot #5.

The same rules applied.

Me: Who should choose steps first?
Daniel: Me. I choose 4.

(We step to spot #4. He sees what happened and gets a bit sad again.)

Me: Let's go 1 step. Good game, Daniel. Let's play again. Do you want to go first or second?

(Daniel uses his finger to count squares: 1, 2, 3, 4. He pauses.)

Daniel: I want to go second.

(I smile.)

Me: Why do you want to go second? Isn't this game about jumping really far? Aren't you nervous that I'm going to jump 4 and you will only jump 1?
Daniel: I want to win.

Me: Hmm... I guess I'll go 1 step.

(This must've thrown a wrench in Daniel's plan. He must've assumed I was going to jump 4 squares. He's a bit rattled. He moves to #1 and then counts: 2, 3, 4, 5. He thinks.)

Daniel: I will jump 4 steps.

I congratulate him and then draw a board from 0-10, 0-15, and then I bring back the 0-20 with a marshmallow. The long story short is that it actually took him multiple days of repeatedly mastering smaller boards to see that the 0-20 was just a 0-15 which was just a 0-10 which was just a 0-5.

Nowadays the game is something he likes to play whenever we have grown-up visitors. Most of the time he announces that he's going to win when he lands on spot #5.

(We go to step

No matter which plate they take you too, you can win.

Plate #16, take 4 steps
Plate #17, take 3 steps
Plate #18, take 2 steps
Plate #19, take 1 step

But how can you guarantee landing on plate #15? By landing on plate #10. And how can you guarantee that? Land on plate #5. And how can you guarantee that? Go second. As I said, the game rewards courtesy, not mad hops.

Imagine a game board that goes from 0-5. Doesn't that make obvious the opening question: would you like to first or second? If you understand that, then you'll see that the same principle applies to a board with 0-10 plates, 0-15, and 0-20. By going second, your opponent will never get to the plate divisible by 5, but they will always make it possible for you to get to it.

?? in JavaScript: the nullish coalescing operator.

Samuel Kendrick — Tue, 02 May 2023 14:55:54 +0000

0 ?? "default";
// 0

false ?? "default";
// false

[] ?? "default"
// []

/** ⚠️ Pay attention.  */

null ?? "default";
// "default"

undefined ?? "default";
// "default"

The ?? operator can be translated as: "return the value on the left UNLESS it's null or undefined. If the value is null or undefined, then use the value on the left of the ??.

<Avatar img={profilePicUrl ?? placeholder}/>

A rambling test-first example

Samuel Kendrick — Wed, 26 Apr 2023 15:09:48 +0000

You've been assigned at ticket! Check it out: https://github.com/VEuPathDB/web-eda/issues/1596

Here's a picture of the mocks:

I've already built out the map and the componentry outlined in pink. The scope of this work is to implement the blue.

People like to say they have good attention to detail. Those folks don't need test-first development (aka TDD). For other mortals, such as myself, I like to have a schematic and then implement code based on that schematic. You know who else does that? Civil engineers. Mechanical engineers. Chemical engineers. Electrical engineers. Basically everyone but software engineers.

My first schematic focused on converting the design into end-user behaviors:

import { render, screen } from '@testing-library/react';
import { MarkerConfigurationMenu } from './MarkerConfigurationMenu';

describe('<MarkerConfigurationMenu />', () => {
  test('users can select a marker type', async () => {  });
  test('when a user selects a marker type, a marker-specific configuration panel appears', async () => {  });
  test('users can configure their marker selection', async () => {  });
});

I also have another user in mind: coworkers. Put another way, my component should have other behaviors which the end-user doesn't care about. For example, the developers using this component will consume it's API (via props). One such behavior would be to fire an event for each time the user updates the marker configuration. As it is, many other components will care about what the user has selected. For instance, this legend needs to know what the user has selected.

Fleshing out the tests

import { render, screen } from '@testing-library/react';
import { MarkerConfigurationMenu } from './MarkerConfigurationMenu';
import { useState } from 'react';

const markerTypes = [
  {
    name: 'Donuts',
    renderConfigurationMenu: function DonutConfigurationMenu() {
      const [frostingSelection, setFrostingSelection] = useState('');
      return (
        <div>
          {frostingSelection.length > 0 ? (
            <p>A donut with {frostingSelection} frosting.</p>
          ) : (
            <></>
          )}
          <label htmlFor="frostingFlavor">
            Frosting flavor
            <select
              onChange={(event) => setFrostingSelection(event.target.value)}
              name="frostingFlavor"
              id="frostingFlavor"
            >
              <option value="">Unfrosted</option>
              <option value="strawberry">Strawberry</option>
              <option value="chocolate">Chocolate</option>
            </select>
          </label>
        </div>
      );
    },
  },
  {
    name: 'Bar plots',
    renderConfigurationMenu: function BarPlotConfigurationMenu() {
      const [barSelection, setBarSelection] = useState('Cheers');
      const [plotSelection, setPlotSelection] = useState('Novel');

      function handleSelection(event: React.ChangeEvent<HTMLSelectElement>) {
        const { name, value } = event.target;
        name === 'bar' ? setBarSelection(value) : setPlotSelection(value);
      }

      return (
        <div>
          <p>
            You will be plotting a {plotSelection} at {barSelection}.
          </p>

          <label htmlFor="bar">
            Bar options
            <select
              onChange={handleSelection}
              value={barSelection}
              name="bar"
              id="bar"
            >
              <option value="Cheers">Cheers (Bostom, MA)</option>
              <option value="The Blue Bar">The Blue Bar (NYC)</option>
              <option value="Harry's Bar">Harry's Bar (Venice, IT)</option>
            </select>
          </label>

          <label htmlFor="plot">
            Plot options
            <select
              onChange={handleSelection}
              value={plotSelection}
              name="plot"
              id="plot"
            >
              <option value="Novel">Novel</option>
              <option value="Bank Heist">Bank Heist</option>
              <option value="Points">Points on a graph</option>
            </select>
          </label>
        </div>
      );
    },
  },
];

describe('<MarkerConfigurationMenu />', () => {
  test('after a user selects a marker type, a marker-specific configuration panel appears', async () => {
    render(<MarkerConfigurationMenu markerTypes={markerTypes} />);

    screen.getByText('Donuts').click();
    screen.getByText('Frosting flavor');
    screen.getByText('Strawberry').click();

    expect(screen.getByText('A donut with strawberry frosting')).toBeVisible();

    screen.getByText('Bar plots').click();

    expect(
      screen.getByText('You will be plotting a novel at Cheers.')
    ).toBeVisible();
  });

  test('users can configure their marker selection', async () => {
    render(<MarkerConfigurationMenu markerTypes={markerTypes} />);

    screen.getByText('Bar plots').click();
    screen.getByLabelText('Bar options').click();
    screen.getByLabelText('The Blue Bar').click();

    expect(
      screen.getByText('You will be plotting a novel at The Blue Bar.')
    ).toBeVisible();
  });
});

I think it'd be wise for the <MarkerConfigurationMenu /> to have one responsibility: rendering the selected marker configuration. The UI for each marker configuration is drastically different for each given marker type. Looky here:

Bar plots:

Donuts:

<MarkerConfigurationMenu /> doesn't actually care about the particulars of the marker configuration.

Actually, I'm going to rename things:

import { render, screen } from '@testing-library/react';
import { MarkerConfigurationSelector } from './MarkerConfigurationSelector';
import { useState } from 'react';

const markerTypes = [
  {
    name: 'Donuts',
    icon: () => {},
    renderConfigurationMenu: function DonutConfigurationMenu() {
      const [frostingSelection, setFrostingSelection] = useState('');
      return (
        <div>
          {frostingSelection.length > 0 ? (
            <p>A donut with {frostingSelection} frosting.</p>
          ) : (
            <></>
          )}
          <label htmlFor="frostingFlavor">
            Frosting flavor
            <select
              onChange={(event) => setFrostingSelection(event.target.value)}
              name="frostingFlavor"
              id="frostingFlavor"
            >
              <option value="">Unfrosted</option>
              <option value="strawberry">Strawberry</option>
              <option value="chocolate">Chocolate</option>
            </select>
          </label>
        </div>
      );
    },
  },
  {
    name: 'Bar plots',
    icon: () => {},
    renderConfigurationMenu: function BarPlotConfigurationMenu() {
      const [barSelection, setBarSelection] = useState('Cheers');
      const [plotSelection, setPlotSelection] = useState('Novel');

      function handleSelection(event: React.ChangeEvent<HTMLSelectElement>) {
        const { name, value } = event.target;
        name === 'bar' ? setBarSelection(value) : setPlotSelection(value);
      }

      return (
        <div>
          <p>
            You will be plotting a {plotSelection} at {barSelection}.
          </p>

          <label htmlFor="bar">
            Bar options
            <select
              onChange={handleSelection}
              value={barSelection}
              name="bar"
              id="bar"
            >
              <option value="Cheers">Cheers (Bostom, MA)</option>
              <option value="The Blue Bar">The Blue Bar (NYC)</option>
              <option value="Harry's Bar">Harry's Bar (Venice, IT)</option>
            </select>
          </label>

          <label htmlFor="plot">
            Plot options
            <select
              onChange={handleSelection}
              value={plotSelection}
              name="plot"
              id="plot"
            >
              <option value="Novel">Novel</option>
              <option value="Bank Heist">Bank Heist</option>
              <option value="Points">Points on a graph</option>
            </select>
          </label>
        </div>
      );
    },
  },
];

describe('<MarkerConfigurationMenu />', () => {
  test('after a user selects a marker type, a marker-specific configuration panel appears', async () => {
    render(<MarkerConfigurationSelector markerTypes={markerTypes} />);

    screen.getByText('Donuts').click();
    screen.getByText('Frosting flavor');
    screen.getByText('Strawberry').click();

    expect(screen.getByText('A donut with strawberry frosting')).toBeVisible();

    screen.getByText('Bar plots').click();

    expect(
      screen.getByText('You will be plotting a novel at Cheers.')
    ).toBeVisible();
  });

  test('users can configure their marker selection', async () => {
    render(<MarkerConfigurationSelector markerTypes={markerTypes} />);

    screen.getByText('Bar plots').click();
    screen.getByLabelText('Bar options').click();
    screen.getByLabelText('The Blue Bar').click();

    expect(
      screen.getByText('You will be plotting a novel at The Blue Bar.')
    ).toBeVisible();
  });
});

Now at this point I have the privilege of showing the specs to my coworkers and get their feedback!

How can I get draggable items to stack on top of each other using react-draggable?

Samuel Kendrick — Thu, 02 Feb 2023 19:46:05 +0000

Hey! Check out my PR: https://github.com/VEuPathDB/CoreUI/pull/140/files

In it I've added a general purpose draggable panel component which renders its children into a panel that can be repositioned by users via drag and drop. To accomplish the dragging/dropping, I depend on react-draggable. I was surprised to see that when I dragged items, the most recently dragged item WAS NOT on top of the other items. Here's what I discovered was happening:

https://youtu.be/bjXWnhiJR0s

YouTube:

Rubber Duck Driven Development: A general purpose draggable menu.

Samuel Kendrick — Wed, 01 Feb 2023 15:00:51 +0000

Song I listened to while starting: https://www.youtube.com/watch?v=N2yg63_vnqg&ab_channel=TheChemicalBrothers-Topic

Hello Rubber Ducky,

Today I'm making a general purpose draggable menu which will be used in many different applications. A concrete example is to emulate something like this big panel:

Or this little panel:

I was given some specifications in a GitHub issue: https://github.com/VEuPathDB/web-components/issues/420.

I read them and tried to come up with some behavior specifications to better define what this component is and what it does. Here's what I came up with:

Panels can be opened and closed.
Panels live somewhere initially.
Users can change where panels live using their cursor/finger.
- This, of course, implies that users can identify the container's handle.
We can put anything into a draggable panel.

Some public-facing API specs for the draggable container:

It should have a defaultPosition.
It should emit a position via an onStop. That's how I'm interpreting "an externally state-controlled position."
It should surface an onClose.
It should also have a setOpen.
It "should be standardised with the EDA's GlobalFiltersDialog (which has a title and close icon, but no handle)."
- Of note: I'm assuming the thing being standardized is the appearance.

I added some testing tools in: https://github.com/VEuPathDB/CoreUI/pull/138. With these I can take a stab at converting a specification in to functional code.

describe("Draggable Panel", () => {
  test("panels live somewhere initially.", () => {});
  test("dragging a panel changes where it lives.", () => {});
  test("when there are two draggables stacked on each other, only the panel the user drags will move.", () => {});
  test("users can close draggable panels.", () => {});
  test("users can open draggable panels.", () => {});
});

In the end

Here are the tests I came up with:

import { fireEvent, render, screen } from "@testing-library/react";
import { useState } from "react";
import { DraggablePanel, DraggablePanelCoordinatePair } from "./DraggablePanel";

describe("Draggable Panels", () => {
  test("dragging a panel changes where it lives.", () => {
    const defaultPosition: DraggablePanelCoordinatePair = { x: 0, y: 0 };
    const panelTitleForAccessibilityOnly = "Study Filters Panel";
    const handleOnDragComplete = jest.fn();
    render(
      <DraggablePanel
        defaultPosition={defaultPosition}
        isOpen
        onDragComplete={handleOnDragComplete}
        onPanelDismiss={() => {}}
        panelTitle={panelTitleForAccessibilityOnly}
        showPanelTitle
      >
        <p>Panel contents</p>
      </DraggablePanel>
    );
    const panelDragHandle = screen.getByText(
      `Close ${panelTitleForAccessibilityOnly}`
    );

    const destinationCoordinates = { clientX: 73, clientY: 22 };

    drag(panelDragHandle, destinationCoordinates);

    /**
     * I really don't like assert on implementation details. If we change React dragging librbaries,
     * this assertion could break and raise a false positive. That said, jsdom doesn't render layouts
     * like a legit browser so we're left with this and data-testids. The data-testid is nice because
     * at least we're in control of that so we can make sure that doesn't change if we swap dragging
     * providers. See conversations like: https://softwareengineering.stackexchange.com/questions/234024/unit-testing-behaviours-without-coupling-to-implementation-details
     */
    const panelFromDataTestId = screen.getByTestId(
      `${panelTitleForAccessibilityOnly} dragged`
    );
    expect(panelFromDataTestId.style.transform).toEqual(
      `translate(${destinationCoordinates.clientX}px,${destinationCoordinates.clientY}px)`
    );

    expect(panelFromDataTestId).toBeTruthy();
    expect(handleOnDragComplete).toHaveBeenCalled();
  });

  test("you can open and close panels", async () => {
    const defaultPosition = { x: 50, y: 50 };

    function ToggleButtonAndDraggablePanel() {
      const [panelIsOpen, setPanelIsOpen] = useState(true);
      return (
        <>
          <button onClick={() => setPanelIsOpen((isOpen) => !isOpen)}>
            Toggle Filters Panel
          </button>
          <DraggablePanel
            defaultPosition={defaultPosition}
            isOpen={panelIsOpen}
            panelTitle="My Filters"
            onDragComplete={() => {}}
            onPanelDismiss={() => setPanelIsOpen(false)}
            showPanelTitle
          >
            <p>I might be here or I might be gone</p>
          </DraggablePanel>
        </>
      );
    }

    render(
      <>
        <ToggleButtonAndDraggablePanel />
        <DraggablePanel
          defaultPosition={defaultPosition}
          isOpen
          panelTitle="My Extra Ordinary Data"
          onDragComplete={() => {}}
          onPanelDismiss={() => {}}
          showPanelTitle
        >
          <p>I will be with you forever.</p>
        </DraggablePanel>
      </>
    );

    expect(
      screen.getByText("I might be here or I might be gone")
    ).toBeVisible();

    const closePanel = screen.getByText("Close My Filters");
    fireEvent.click(closePanel);

    expect(
      screen.queryByText("I might be here or I might be gone")
    ).not.toBeVisible();
    expect(screen.queryByText("I will be with you forever.")).toBeVisible();

    fireEvent.click(screen.getByText("Toggle Filters Panel"));
    expect(
      screen.getByText("I might be here or I might be gone")
    ).toBeVisible();
  });
});

/**
 * So we're pretty limited as regards js-dom and dragging. Here's what I would like to do:
 * 1. Simulate dragging events on the draggable element.
 * 2. Find the element, getBoundingClientRect for the element
 * 3. Assert that the coordinates moved predictably.
 *
 * Here's the reality: jsdom doesn't do any rendering, so getBoundingClientRect() always
 * returns 0,0,0,0. That won't change (even foreseeable long-term).
 * You can try to mock the function to emulate the results you'd expect.
 * https://github.com/jsdom/jsdom/issues/1590#issuecomment-243228840
 *
 * @param element
 * @param destinationCoordinates
 */
function drag(
  element: HTMLElement,
  destinationCoordinates: { clientX: number; clientY: number }
): void {
  fireEvent.mouseDown(element);
  fireEvent.mouseMove(element, destinationCoordinates);
  fireEvent.mouseUp(element);
}

https://github.com/VEuPathDB/CoreUI/pull/140/files

The number of elements in a power set of size <= 1 is the size of the original set + 1 more element: the empty set .

Samuel Kendrick — Thu, 16 Jul 2020 14:59:55 +0000

Suppose $∣ A ∣ = m$ . What is the size of this set:

\{X \in \mathscr{P}(A) \in : |X| \leq 1 \} |

Let's start with a specific example:

\{X \in \mathscr{P}(\{1,2,3\}) \in : |X| \leq 1 \} |

First, let's create the power set, stopping once we hit an element whose size is greater than 1:

{\mathscr{P}(\{1,2,3\})} = \{\emptyset, \{1\}, \{2\}, \{3\} \}

Notice that the number of elements of size $≤1\leq 1$ is the size of the original set + 1 more element: the empty set.

Thus:

\{X \in \mathscr{P}(A) \in : |X| \leq 1 \} | = m+1

Sorting ISO 8601 timestamps

Samuel Kendrick — Thu, 16 Jul 2020 14:26:34 +0000

Let's suppose I have a list of timestamps:

timestamps = [
  '2020-06-02T16:47:50Z',
  '2020-05-08T01:25:10Z',
  '2020-05-08T19:51:29Z',
  '2020-06-04T20:23:02Z',
  '2020-05-27T02:23:14Z',
  '2020-05-12T16:32:08Z',
  '2020-05-06T01:58:21Z',
  '2020-05-14T16:11:31Z',
  '2020-05-08T14:25:36Z',
  '2020-05-22T20:48:13Z',
  '2020-05-10T02:43:44Z'
];

Maybe a more "real-world" example would be scenario where you have a list of dictionaries and you want to sort by their created_date attribute. How would you do it?

If we wanted to sort our timestamps we could parse the date string into a date object and then use some compare function to correctly sort the list.

Fortunately, there's a nicer solution! Some date formats, such as ISO 8601 can be sorted merely as strings.

How can this be?

The ISO 8601 format is lexicographically ordered. If you have an ordered set of names: "Carlton" and "Carlyle." When ordered, "Carlton" precedes "Carlyle" because the 5th letter "t" is less than "y".

If you have two timestamps: "2020-05-08T19:51:29Z" and "2020-05-08T01:25:10Z", they differ at the 12th character and, because of the leading 0, the first timestamp comes after the second timestamp.

This is all do say that you can sort your timestamps very easily:

timestamps = [
  '2020-06-02T16:47:50Z',
  '2020-05-08T01:25:10Z',
  '2020-05-08T19:51:29Z',
  '2020-06-04T20:23:02Z',
  '2020-05-27T02:23:14Z',
  '2020-05-12T16:32:08Z',
  '2020-05-06T01:58:21Z',
  '2020-05-14T16:11:31Z',
  '2020-05-08T14:25:36Z',
  '2020-05-22T20:48:13Z',
  '2020-05-10T02:43:44Z'
];
timestamps.sort() # Yay!

The Cartesian product of a set and the empty set

Samuel Kendrick — Thu, 16 Jul 2020 00:43:08 +0000

The cartesian product is the product of two sets. The resulting product is a set of pairs, one element belonging to $A$ and one element belonging to $B$ .

This can expressed as:

\times B = \{ (x,y) : x \in A, y \in B \} }

So what happens if we try to take the cartesian product of a set and the empty set? $\times \emptyset}$ ?

We end up with: $\times \emptyset} = \emptyset$ . This is because we try to build a set like this: $\times B = \{ (x,y) : x \in A, y \in B \} }$ , but $B$ is empty.

It is impossible to create this resulting set of pairs because one of the sets is the empty set. As such, not a single element can be produced from $B$ , so our resulting set is the empty set.

Any tree with at least two vertices must have at least two vertices of degree one.

Samuel Kendrick — Thu, 28 May 2020 14:04:20 +0000

Proposition: Any nontrivial tree must have at least two vertices of degree one (sometimes called leaves)

Here's a proof by contradiction:

Let $T$ be a nontrivial tree, that is, one with at least two vertices. In fact, let's draw one, just for fun:

        o (v1)
      /   \
(v0) o     o (v2)
         / 
        o (v3)

I might be easier to look at the tree like this:

        o (v0 = u)
        |
        o (v1)
        |
        o (v2)
        | 
        o (v3 = v)

Of note: I labeled v0 as u and v_3 as v. More on that later.

Let P be a path in T of the longest possible length. It's alright if your tree has more than one path of equal length, so long as we choose one with the longest possible length. As mentioned above, u and v represent the start and finish vertices of P. So our P is u, v1, v2, v.

Next, suppose, contrary to the proposition, that there are NOT two vertices of degree one. This brings us to why we care about P. The longest path, in any tree, contains a start and end vertex of degree one.

Both ends of P must be vertices with degree one, satisfying the "at least two vertices of degree one" part of the original proposition. But we're supposing that there are NOT two vertices of degree one.

That means either u or v need to be adjacent to one more vertex in T. Let's pick $u$, the start vertex and we will call the adjacent vertex u'.

Which vertex is u'? u is already adjacent to a vertex on the path P (v1). If u' was another vertex on the path P, then we'd get a cycle. I've illustrated this below:

        o (v0 = u)
      / |
     |  o (v1)
     |  |
      \ |
        o (v2 = u')
        | 
        o (v3 = v)

We cannot have cycles in a tree, since a tree is an undirected acyclic graph. So this can't be.

However, if we think u' is a vertex adjacent to u, but not on the path P, then we will contradict our previous choice of P as longest path since there would be a vertex preceding u.

Exploring the definition of a tree

Samuel Kendrick — Mon, 25 May 2020 20:38:53 +0000

When you look at the definition of a tree on Wikipedia, you'll see something like:

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

The first bit of that definition may seem weird at first. An acyclic undirected graph might make more sense. But it's the first bit of the definition that explicitly highlights an essential property of a tree.

A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique path.

Let's prove it!

Assume graph T is a tree. Let u and v be distinct vertices in that assumed tree. If T has one vertex, then the conclusion is satisfied automatically as there is only one path to get to one vertex.

Now, we must show two parts:

There is a path.
There is not more than one path.

The first part is satisfied by our assumption that T is a tree. Recall that trees are acyclic connected graphs. Check ✔️.

Next, to show that the path is unique, suppose that our tree actually has two paths between u and v.

If there are two paths from u to v, we know that these paths start the same way and differ somewhere along the way. Because these paths go to the same end, the paths must converge at the same vertex.

In fact, they must diverge at a common vertex u' and converge at a common vertex v'. Look what that gives us:

   u
   u'
  / \
 x   y
  \ /
   v'
   v

We arrived at a contradiction regarding the "acyclic" property of trees. Trees are "acyclic connected graphs." What we have shown above is a cyclic connected graph, not a tree.

Handshaking lemma / Degree sum formula

Samuel Kendrick — Sat, 23 May 2020 20:39:37 +0000

Behold, the degree sum formula:

The degree sum formula states that, given a graph G = (V,E), the sum of the degrees is twice the number of edges. Let's look at K3, a complete graph (with all possible edges) with 3 vertices.

First, recall that degree means the number of edges that are incident to a vertex. A vertex is incident to an edge if the vertex is one of the two vertices the edge connects. In the case of K3, each vertex has two edges incident to it. Actually, for all K graphs (complete graphs), each vertex has n-1 degrees, n being the number of vertices. Dope.

So, for each vertex in the set V, we increment our sum by the number of edges incident to that vertex. Or, in another way, construct a degree sequence for a graph and sum it: sum([2, 2, 2]) # 6. This sum is twice the number of edges. Our graph should have 6 / 2 edges.

The "twice the number of edges" bit may seem arbitrary. But each edge has two vertices incident to it. In the degree sum formula, we are summing the degree, the number of edges incident to each vertex. A degree is a property involving edges. Edges are connections between two vertices. Summing the degrees of each vertex will inevitably re-count edges.

Properties we can derive from this formula

Anything multiplied by 2 is even. Since the sum of degrees is two times the number of edges the result must be even and the number of edges must be even too.

With the above knowledge, we can know if the description of a graph is possible. This is useful in a puzzle such as the one I found in this book:

At a recent math seminar, 9 mathematicians greeted each other by shaking hands. Is it possible that each mathematician shook hands with exactly 7 people at the seminar?

Each mathematician would shake the hand of 7 others which amounts to shaking hands with every mathematician minus yourself and one other person.

A graph may not have jumped out at you, but this puzzle can be solved nicely with one. Think of each mathematician as a vertex and a handshake as an edge.

Can we have a graph with 9 vertices and 7 edges? Applying the degree sum formula, we can say no.

When we sum the degrees of all 9 vertices we get 63, since 9 * 7 = 63. Since the sum of degrees is twice the number of edges, we know that there will be 63 ÷ 2 edges or 31.5 edges. Since half a handshake is merely an awkward moment, we know this graph is impossible.

I hate telling mathematicians that they can't shake hands. Can we have 9 mathematicians shake hands with 8 other mathematicians instead?

Can we have a graph with 9 vertices and 8 edges?

Summing 8 degrees 9 times results in 72, meaning there are 36 edges.

How many squares of any size are there on an 8x8 chessboard?

Samuel Kendrick — Tue, 04 Feb 2020 15:09:23 +0000

The chessboard is an inessential detail, so let's re-phrase the question:

How many squares, of any size, are there on an 8x8 grid?

Eventually, it'll be:

How many squares, of any size, are there on an n x n grid?

Some tools that I'll be using to solve this problem:

Sequences
Basic arithmetic
A nifty property of sequences called Δ-k constants and which help us find "closed" formulas (more on that later)

As is common in problem solving, the simplest examples illustrate the problem and give a starting point.

A 0x0 grid

There are zero squares of any size.

A 1x1 grid

There is one square of size 1x1.

A 2x2 grid

This is where the "of any size" bit takes on meaning. In a 2x2 grid there are actually 5 squares "of any size." This is because a 2x2 grid contains 4 1x1 squares and then a single square of size 2x2.

You can see here that there are 5 squares of multiple sizes. There are four 1x1 squares and then a 2x2 square (the dashed-square). There are 4 + 1 = 5 total squares.

A 3x3 grid

A 3x3 grid is nothing but nine 1x1 squares, four 2x2 squares, and one 3x3 square. I've highlighted one of the four 2x2 squares (they contain numbers 1,2,4,5). There are 9 + 4 + 1 = 14 total squares.

A pattern emerges

Enter sequences:

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order does matter

Let's write the total number of squares as a sequence. The "index" of each item in the sequence represents n in the n x n grid:

0, 1, 5, 14

Each element in our total number of squares sequence can be defined as a the sum of all previous totals up to, and including, the current total. Put another way:

0x0 -> 0 squares (0)
1x1 -> one 1x1 square + zero 0x0 squares (1 + 0)
2x2 -> four 1x1 squares + one 2x2 square + zero 0x0 squares (4 + 1 + 0)
3x3 -> nine 1x1 squares + four 2x2 squares + one 3x3 square + zero 0x0 squares (9 + 4 + 1 + 0)

If n = 3, the number of squares on your n x n grid is: 0¹ + 1² + 2² + 3² or 0 + 1 + 4 + 9 = 14.

Answering our original question is now easy.

How many squares of any size are there on an 8x8 grid?

You just sum the squares from 0 to n.

sum([i**2 for i in range(0, 9)]) # 204

Recall that range counts from 0 up to 9, but not including 9.

Finding a closed formula

We can find a closed formula to calculate this without the summation. For example, you could add all the terms of a sequence of 1, 2 ,3, ..., n to find the total. Or your could use this handy equation:

total = (n(n+1)) / 2

Compare: 1+2+3+4+5 = 15 and (5(5+1))/2 = 15.

Let's take our sequence and extend it with a few more elements:

1, 5, 14, 30, 55

We can find a pattern of sorts by taking the differences between terms. We can form another sequence of terms (the differences) which will always be one element shorter than the original.

1, 5, 14, 30, 5
4, 9, 16, 25
5, 7, 9
2, 2

We took differences three times in order to reach a constant. What we just did there was find the Δ-k constant. In this case, Δ³ constant.

This is important for this reason:

The closed formula formula for a sequence will be a degree k polynomial if and only if the sequence is Δ^k-constant

This means our closed formula will be a degree k (3) polynomial or:

an = an³ + b² + cn + d

Note: an represents the nth element of a, which is our sequence: 0, 1, 5, 14, 30, 55. The 0th term is 0, the 1st term is 1, the second term is 5, etc.

a0 = 0 = a(0)³ + b(0)² + c(0) + d

The above simplified to: d = 0—an important piece of information.

a1 = 1 = a(1)³ + b(1)² + c(1) + 0
a1 = 1 = a + b + c

a2 = 5 = a(2)³ + b(2)² + c(2) + 0
a2 = 5 = 8a + 4b + 2c

a3 = 14 = a(3)³ + b(3)² + c(3) + 0
a3 = 14 = 27a + 9b + 3c

Now we have a system of equations which we can solve for to get the values of a, b, and c.

a1 = 1 = a + b + c
a2 = 5 = 8a + 4b + 2c
a3 = 14 = 27a + 9b + 3c

To save time, I will wave my hand and solve that system:

a = 1/3
b = 1/2
c = 1/6

With these values, we now have our closed formula:

an = 1/3(n)³ + 1/2(n)² + 1/6(n)

If n = 8: 1/3(8)^3 + 1/2(8)^2 + 1/6(8) = 204
If n = 800: 1/3(800)^3 + 1/2(800)^2 + 1/6(800) = 170986800