August 23, 2025

Module 3 - Warm Up

Maximizing Profit: Chocolate Factory

Setup

Let $M$ = boxes of milk chocolate per day
Let $D$ = boxes of dark chocolate per day

Constraints $\begin{aligned} M &\le 500 \quad \text{(milk demand)}\\ D &\le 200 \quad \text{(dark demand)}\\ M + D &\le 600 \quad \text{(daily capacity)}\\ M, D &\ge 0 \end{aligned}$

Objective $\max\; 10M + 30D$

Existential part: a plan that achieves $10{,}000

Take $(M,D)=(400,200)$.

Feasibility check: $400 \le 500,\quad 200 \le 200,\quad 400+200=600 \le 600$

Profit: $10\cdot 400 + 30\cdot 200 = 4000 + 6000 = 10{,}000$

Universal part: no plan can exceed $10{,}000 From the constraints, $\begin{aligned} M + D &\le 600 \quad \Rightarrow \quad 10M + 10D \le 6000,\\ D &\le 200 \quad \Rightarrow \quad 20D \le 4000. \end{aligned}$ Add them: $(10M + 10D) + (20D) \le 6000 + 4000 \;\Rightarrow\; 10M + 30D \le 10{,}000.$ Thus every feasible plan has profit at most $10{,}000, so the plan above is optimal.

Dual (certificate of optimality) Primal (above) dual is $\begin{aligned} \min\;& 500y_1 + 200y_2 + 600y_3 \\ \text{s.t. }& y_1 + y_3 \ge 10 \quad \text{(for } M\text{)}\\ & y_2 + y_3 \ge 30 \quad \text{(for } D\text{)}\\ & y_1,y_2,y_3 \ge 0. \end{aligned}$ Choose $(y_1,y_2,y_3) = (0,20,10),$ which is feasible since $0+10=10\ge10$ and $20+10=30\ge30$. Its value is $500\cdot 0 + 200\cdot 20 + 600\cdot 10 = 4000 + 6000 = 10{,}000.$ By weak duality, every primal feasible plan has profit $\le 10{,}000$. Since we have a primal plan achieving $10{,}000, it is optimal (strong duality).

Geometric intuition

The objective prefers dark chocolate (higher profit per box).
Produce dark up to its demand: $D=200$.
Use remaining capacity for milk: $M=600-200=400$.
This is the corner point where $D=200$ and $M+D=600$ intersect, yielding the maximum.

Answer

Optimal production plan: $M=400$, $D=200$.
Maximum profit: $10{,}000.

Simple Card Game (Draw two cards)

We are given all two-digit numbers: 10, 11, 12, …, 99.
We want to select as many numbers as possible under the constraint that no two chosen numbers sum to 100.
In other words, for every chosen $x$, the number $100-x$ cannot also be chosen.
The question is: what is the maximum possible number of such integers?

Solution Let us analyze step by step.

Pairing numbers
- Consider the smallest number 10. Its complement with respect to 100 is 90.
  Hence, from the pair $(10,90)$ we can take at most one number.
- Similarly, $(11,89), (12,88), …, (49,51)$ are all disjoint pairs.
- In total, there are 40 such pairs.
Free numbers
- The number 50 is special: its complement is itself. Since we have only one copy of 50, we can take it without conflict.
- The numbers 91, 92, …, 99 also have no valid complements in the two-digit range, so they can all be chosen.
- Thus, there are $1+9=10$ such “free” numbers.
Upper bound
- From each of the 40 pairs, we can select at most one element.
- Along with the 10 free numbers, the total maximum size is: $40 + 10 = 50.$ So no solution can exceed 50 numbers.
Achievability
- To see that 50 is achievable, consider the set $\{50, 51, 52, \ldots, 99\}.$ This set contains 50 numbers.
  Any two chosen numbers sum to at least $50+51=101$, which is never equal to 100.
  Hence, this is a valid solution.

Conclusion The maximum number of two-digit integers one can select with no two summing to 100 is: $\boxed{50}.$

Maximum Number of Rooks on a Chessboard

What is the maximum number of rooks that one can place on an $8\times 8$ chessboard such that no two rooks attack each other?

A rook moves any number of squares vertically or horizontally.
Thus, if two rooks share the same row or the same column, they attack each other.

The pigeonhole principle states:
If $n$ pigeons are placed into $m$ boxes with $n>m$, then at least one box contains more than one pigeon.

Think of the 8 rows as “boxes” and rooks as “pigeons.”
If there were more than 8 rooks, then by the pigeonhole principle, at least one row would contain at least two rooks.
But if two rooks share a row, they attack each other.
Therefore, at most 8 rooks can be placed without conflict.

Placing 8 rooks is straightforward:

Put one rook in each row and each column.
Example: place rooks along the diagonal:
$(1,1), (2,2), (3,3), \dots, (8,8).$
This arrangement ensures no two rooks attack.
Upper bound: at most 8 rooks (pigeonhole principle).
Achievable: exactly 8 rooks (diagonal or other one-per-row-and-column placements).
Hence the maximum is: $\boxed{8}$

There are many optimal solutions:
any placement with one rook per row and per column is valid.

Maximum Number of Knights on a Chessboard

What is the maximum number of knights that can be placed on an $8\times 8$ chessboard such that no two knights attack each other?

A knight moves in an L-shape: two squares in one direction and one square perpendicular.
Importantly:

A knight on a white square attacks only black squares.
A knight on a black square attacks only white squares.

If we place knights on all 32 white squares, then:

None of these knights attack each other, because a knight on white only attacks black.
Thus, we immediately have a valid solution with: $32 \;\text{knights}.$

Suppose we try to place more than 32 knights.

Clearly, 64 knights is impossible, since many pairs of knights would attack.
Consider the bottom-left corner square. It conflicts with the square two up and one right.
So these two form a forbidden pair: at most one knight can be placed between them.

If we can partition the entire chessboard into disjoint pairs of squares such that the two squares in each pair attack each other, then:

From each pair, we can select at most one knight.
Since there are $64/2=32$ pairs, at most 32 knights can be placed.

Indeed, the board can be partitioned into $2\times 4$ rectangles.

Each $2\times 4$ rectangle has 8 squares.
Inside it, we can group the squares into 4 attacking pairs.
Thus, at most 4 knights can be placed inside such a rectangle.
Since the $8\times 8$ board can be fully covered by 8 such rectangles, we get a total bound: $8 \times 4 = 32.$
We found a construction with 32 knights (all on white squares).
We proved that no arrangement can exceed 32 knights.

Hence, the maximum number of knights on a chessboard with no two attacking is: $\boxed{32}$

Maximum Number of Bishops on a Chessboard

Problem

What is the maximum number of bishops that can be placed on an $8\times 8$ chessboard such that no two bishops attack each other?

Reminder: Bishop Movement

A bishop moves diagonally across the board.
Thus, if two bishops share the same diagonal, they attack each other.

Step 1: Partition into Diagonals

The board can be partitioned into 15 diagonals running from bottom-left to top-right.
Each diagonal can hold at most one bishop (otherwise they would attack).
This gives a first upper bound: $\text{Maximum} \leq 15$

Step 2: Tightening the Upper Bound

Look at diagonal 1 (bottom-left corner). It contains just one square.
Similarly, diagonal 15 (top-right corner) also contains just one square.
We cannot place bishops on both of these simultaneously, since they lie on the same other diagonal.
Thus, the true maximum is reduced to: $\text{Maximum} \leq 14$

Step 3: Constructing a Solution

It is indeed possible to place 14 bishops without conflict:

Choose one bishop on each diagonal numbered $2,3,\dots,15$ except for one of the extremes.
With careful placement, no two bishops attack each other.

Step 4: Conclusion

Upper bound: 14 bishops.
Achievability: 14 bishops (by explicit construction).

Therefore, the maximum number of bishops that can be placed on an $8\times 8$ chessboard with no two attacking is: $\boxed{14}$

Subset without x and 2x

Choose the maximal number of integers among 1..50 that can be selected if we are not allowed to select n and 2n at at same time.

Did I think about it - no, I just started clicking after one - whatever was clickable.

Solution

Idea: partition the numbers into chains formed by repeatedly doubling, each chain starting at an odd number.
For an odd starter $s$ the chain is $s,\;2s,\;4s,\;8s,\;\dots$ stopping when the next doubling exceeds $50$. Every integer $1\le n\le 50$ belongs to exactly one such chain (its unique chain is obtained by repeatedly dividing by $2$ until odd). Numbers of the form $x$ and $2x$ always lie in the same chain, and there are no conflicts between different chains. Thus the problem reduces to choosing, independently in each chain, a largest set that contains no two consecutive elements of that chain.

Optimal choice in a single chain

If a chain has length $L$, the largest number of elements we can pick from that chain with no two consecutive (no $x$ and $2x$) is $\left\lceil\frac{L}{2}\right\rceil.$ (Choose every second element starting from the first.)

List of chains (starter → chain) $\begin{aligned} 1&:\; 1,2,4,8,16,32 & (L=6)\\ 3&:\; 3,6,12,24,48 & (L=5)\\ 5&:\; 5,10,20,40 & (L=4)\\ 7&:\; 7,14,28 & (L=3)\\ 9&:\; 9,18,36 & (L=3)\\ 11&:\; 11,22,44 & (L=3)\\ 13&:\; 13,26 & (L=2)\\ 15&:\; 15,30 & (L=2)\\ 17&:\; 17,34 & (L=2)\\ 19&:\; 19,38 & (L=2)\\ 21&:\; 21,42 & (L=2)\\ 23&:\; 23,46 & (L=2)\\ 25&:\; 25,50 & (L=2)\\ 27,29,31,\dots,49&:\; \text{each a singleton }(L=1) \end{aligned}$

Compute the best pick from each chain: take $\lceil L/2\rceil$ from each chain. Summing over all odd starters $1,3,5,\dots,49$ gives $\sum_{\text{odd }s\le50} \left\lceil\frac{L_s}{2}\right\rceil = 33.$

Concrete optimal selection (one example) Pick every other element in each chain starting with the first. One such maximal set (sorted) is $\{1,3,4,5,7,9,11,12,13,15,16,17,19,20,21,23,24,25,27,28,29,31,33,35,36,37,39,41,43,44,45,47,48,49\},$ which has size $33$ and contains no pair $x,2x$.

make this image smaller and add shading

Optimality

By partitioning into chains we reduced the problem to independent subproblems, and we chose the maximal possible number from each chain. Therefore no larger global selection exists.

Answer $\boxed{33}$

Maximum Number of Two Digit Integers (figure out the correct location of this)

Question 1 There are 90 cards with all two-digit numbers on them:

$10, 11, 12, …, 98, 99$

A player takes some of these cards simultaneously. For each card taken she gets $1. However, if the player takes two cards that add up to 100 (say, 23 and 77), she loses all the money. How much could she get?

In mathematical language: What is the maximum number of two-digit integers (10,11,…,99) that one can select satisfying the following condition: no two different selected integers have sum 100?

FROM BELOW THIS I NEED TO REFACTOR AND MAKE NOTES AFTER CHATGPT 5 COMES BACK

https://braintoblueprinttobuild.wordpress.com/2017/05/28/two-classic-chess-problems-and-how-to-solve-them-the-hard-way/

N Queens

Place 2 queens such that no two attack each other. Click on a cell to add or remove a queen. Grid 2x2
- Solution: It’s impossible
Place 3 queens such that no two attack each other. Click on a cell to add or remove a queen. Grid 3x3
- Solution: It’s impossible
Place 4 queens such that no two attack each other. Click on a cell to add or remove a queen. Grid 4x4
- Solution: It’s possible
Place 5 queens such that no two attack each other. Click on a cell to add or remove a queen. Grid 5x5
- Solution: It’s possible

Hello and welcome to the lesson Computer Search. To prove that an object satisfying some particular properties exists, it is actually enough to construct and present such an object. At the same time, there are cases when it is not so easy to do this by hand, and it is exactly the situation when it makes perfect sense to us, computers to help us. And this is exactly the thing that we’re going to do in this lesson. Namely, what we will consider through challenging puzzles,namely n queens puzzles and 16 diagonals puzzle. If you try them, you will notice that it is indeed not so easy to find the solution. Instead of constructing such a solution by hand, we’re going to implement this simple program that is going to help us to find a solution in a blink of an eye. Play video starting at ::52 and follow transcript0:52 So we start with the N Queens puzzle. Let me first remind you how the chess queen moves. So it moves horizontally, diagonally, and vertically. So, for example, the queen that you see here on the slide can move along either this vertical line or horizontal line or two diagonal lines. Okay. Then the natural question is the following. Given an n x n chessboard, your goal is to place exactly n queens on this board such that no two queens attack each other. Play video starting at :1:31 and follow transcript1:31 Okay? So, first of all, we know that the solution for this puzzle exists whenever n is at least four. At the same time, if you try to solve this puzzle by hand, you will notice that already for n equals eight, it is not so easy to find it by hand. Not to say about n equals 20. So let’s try to find a solution and let’s try to find and implement a computer program that will find a solution almost immediately. First of all, let’s try to understand how to represent a particular solution in our problem. And for this, let’s notice that if there is a solution that in every column, there must be exactly one, one queen. Play video starting at :2:20 and follow transcript2:20 Why is that? Well exactly, because if there are at least two queens in some column, then they definitely must attack each other. So there must be at most one queen in each column. At the same time, if there is a column without the queen, this means basically is that in total, there are strictly less than n queens. And similarly we conclude that in each rows there must be exactly one queen. Okay. Now let’s consider the following solution for the case where n, the size of the board is equal to four. Play video starting at :2:57 and follow transcript2:57 So in this case we have 4 x 4 board and there are four queens, exactly one queen in each row and exactly one queen in each column, such that they do not attack each other. So what the title of the slide claims here, is that this solution can be represented as a permutation. You see the left index of the columns and of the rows by numbers starting from zero to n minus one. So in this case n equals 4, so n minus one equals three. Okay, so now let’s represent the corresponding placement of queens by the following permutation of the numbers 0, one, two, three. So how it is represented by this permutation? Well it is easy to see. Play video starting at :3:47 and follow transcript3:47 So this is an array, right? It is of size four. This is its indices 0, one, two, three. So the contents of the cell one actually tells of that in the zero’s column, this is the zero’s column and this the zero cell, we have a queen in the first row. This is the queen in the first row, right? And this exactly corresponds to this one. For the second column, that is column number one because we start from zero, we have three in this cell and this exactly indicates the fact that for this column, we have a queen standing at the third row in this column and so on. Play video starting at :4:43 and follow transcript4:43 So, at this point, it should be clear that every correct solution can be represented by a permutation. This is exactly because in every row and in every column, we have a single queen. At the same time, not every permutation defines a solution and this is shown here on the slide. And so in the left, we have our previous solution and in the right, we have also some permutation which defines some placement of queens such that in every row and in every column, there is exactly one queen. At the same time, it is not a solution, right? Because we have two queens here on the same diagonal. So they attack each other. Play video starting at :5:28 and follow transcript5:28 So we definitely need some procedure that we’ll check whether the given permutation is indeed a solution. So we need to implement the procedures that will be given a permutation and it will all prove true even though I believe in this permutation, in this placement of queens on the n by n board, there are no two queens that stay on the same diagonal. So let’s try to design a formula which will tell us when two queens stay on the same diagonal. This is our initial picture, so it shows our initial queen and it shows all the positions where it can move. So when I claim in the following, two queens stay on the same diagonal, consider for example, this queen and for example this queen. So they stay on the same diagonal because this horizontal shape exactly equal its vertical shape, right? And this is true for all the positions shown here on the slide. Play video starting at :6:37 and follow transcript6:37 So in this particular case we have four cells here and four cells here. Now let’s consider for example this queen. So these two guys stay on the same diagonal exactly because the difference between their coordinates with respect to the columns is equal to the distance. It is equal to three. In this case, it is equal to three with respect to rows. And so right here, we see a formula. So, if we have two cells with coordinates I1 and J1 and I2 and J2, so this means that we have a queen standing at I’s row and J’s column and we have another queen standing at I2 row and J2 column. Play video starting at :7:26 and follow transcript7:26 So then they stay on the same diagonal, if and only if, the absolute value between I1 and I2 is equal to the absolute value between J1 and J2. Right? So this is our formula and it allows us to immediately implement a simple program, just four lines of code that will check whether a given permutation is indeed a solution. So to check this, we do the following. We just, given the permutation, we go through all possible indices of rows, I1 and I2. So here we just iterate for all possible such queries using combinations from itertools. So then we just check whether the absolute value of I1 and I2 is equal to the absolute value of J1 and J2, where J1 is computed as permutation of I1. Play video starting at :8:27 and follow transcript8:27 So this is J1 and J2 is computed as a permutation of I2. So if this absolute value is inside for at least for some pair of I1 and I2, this basically means that there are two queens that attack each other. In this case, we immediately return false. If there is no such player, we return true. So after this procedure is implemented, we do a small sanity check. We just check whether for the previously considered examples, the first one is indeed a solution and the second one is indeed not a solution. Okay. So when given such a check whether a given permutation is a solution or not, we can actually implement the whole program for finding a solution for the eight by eight board for example. Play video starting at :9:27 and follow transcript9:27 So this is our procedure that checks whether a given permutation is a solution or not. And then what remains to be done is just to iterate through all possible permutations. And fortunately enough, in Python we can do this very easily. So we just iterate through all possible permutations and for each one we check whether it is a solution or not. If it is a solution, we print it and we stop immediately, okay? And this is basically it. So if you run this program, you will notice that it will find a solution for n equal to eight, almost immediately. Play video starting at :10:9 and follow transcript10:09 At the same time, already for n equal to 13, for example, it takes a noticeable time. Okay. Not to say about n equal to 20, it will never stop for n equal to 20. In the next video, we will actually optimize our problem so that it works quite fast even for n equal to 20.

Computer Search • There are cases when a solution exists, but it is not easy to construct it by hand

Computer Search • There are cases when a solution exists, but it is not easy to construct it by hand • Let computers do the job!

Computer Search • There are cases when a solution exists, but it is not easy to construct it by hand • Let computers do the job! • For two puzzles (n queens and 16 diagonals), we will implement a program that will solve a puzzle on your laptop in blink of an eye Outline N Queens: Brute Force Search N Queens: Backtracking 16 Diagonals Chess Queen A chess queen moves vertically, horizontally, or diagonally Chess Queen A chess queen moves vertically, horizontally, or diagonally N Queens Problem Problem Is it possible to place n queens on an n × n chessboard such that no two queens attack each other? Computer Search • It is known that this is possible for all n ≥ 4

Computer Search • It is known that this is possible for all n ≥ 4 • But already for n = 8 it is not easy to construct a solution by hand Speculating • Since we are placing n queens on an n × n board, there should be exactly one queen in each column

Speculating • Since we are placing n queens on an n × n board, there should be exactly one queen in each column • If there are two queens in a column, they attack each other. Hence at most one queen in each column • If there is a column without a queen, then the total number of queens is less than n • For the same reason, there should be exactly one queen in each row Solution is a Permutation Solution is a Permutation 0 0 1 1 2 2 3 3 Solution is a Permutation 1 3 0 2 0 0 1 1 2 2 3 3 But Not Every Permutation is a Solution 1 3 0 2 3 1 0 2 ✓ ✗

But Not Every Permutation is a Solution 1 3 0 2 3 1 0 2 ✓ ✗ How to check whether a permutation is a solution? Cells in the Same Diagonal 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 cells [i1, j1] and [i2, j2] are on the same diagonal, if and only if |i1 − i2| = |j1 − j2| Is a Solution? import i t e r t o o l s as i t def i s _ s o l u t i o n ( perm ) : for ( i1 , i 2 ) in i t . combinations ( range ( len ( perm ) ) , 2 ) : i f abs ( i 1 − i 2 ) == abs ( perm [ i 1 ] − perm [ i 2 ] ) : return F alse return True a s s e r t ( i s _ s o l u t i o n ( [ 1 , 3 , 0 , 2 ] ) == True ) a s s e r t ( i s _ s o l u t i o n ( [ 3 , 1 , 0 , 2 ] ) == F alse ) Brute Force Search Program import i t e r t o o l s as i t def i s _ s o l u t i o n ( perm ) : for ( i1 , i 2 ) in i t . combinations ( range ( len ( perm ) ) , 2 ) : i f abs ( i 1 − i 2 ) == abs ( perm [ i 1 ] − perm [ i 2 ] ) : return F alse return True for perm in i t . permutations ( range ( 8 ) ) : i f i s _ s o l u t i o n ( perm ) : p rint ( perm ) e x i t ( ) Conclusion • The program finds a solution for n = 8 immediately

Conclusion • The program finds a solution for n = 8 immediately • But already for n = 13 takes too long

Conclusion • The program finds a solution for n = 8 immediately • But already for n = 13 takes too long • Next part: will optimize the program so that it is able to find a solution quickly even for n = 20

import itertools as it

def is_solution(perm):
    for (i1, i2) in it.combinations(range(len(perm)), 2):
        if abs(i1 - i2) == abs(perm[i1] - perm[i2]):
            return False

    return True

for perm in it.permutations(range(8)):
    if is_solution(perm):
        print(perm)
        exit()

https://www.youtube.com/watch?v=Ph95IHmRp5M&ab_channel=NeetCode