Module 2 - How to find an Example

Magic Squares

Multiplicative Magic Squares

6 digit number starting with 100 divisible by 9271

3 digit number that produces a remainder 1 when divided by 2, 3, 4, 5, 6, 7

for i in range(101, 999, 2):
    if (i % 6 == 1) and (i % 4 == 1) and (i % 5 == 1) and (i % 7 == 1):
        print(i)
# but the simpler way of doing this is
# N - 1 is some number divisible by 2, 3, 4, 5, 6, 7
# N - 1 is 2 * 2 * 3 * 5 * 7 
print(2 * 2 * 3 * 5 * 7)
# therefore N = (2 * 2 * 3 * 5 * 7) + 1

We are looking for a 3-digit number $N$ such that

This means that $N-1$ must be divisible by all of $2,3,4,5,6,7$. The lowest common multiple is: \(\text{lcm}(2,3,4,5,6,7) = 420.\)

Answer: $420 + 1 = 421$

The second number can be found doing:

Answer: $(420 * 2) + 1 = 841$

# Find 3-digit number N such that N % m = 1 for m = 2, 3, 4, 5, 6, 7
# This means N - 1 is divisible by 2, 3, 4, 5, 6, 7
# Since 4 = 2 * 2 and 6 = 2 * 3, we need N - 1 divisible by 2, 3, 4, 5, 6, 7
# Compute product 2 * 2 * 3 * 5 * 7 = 420 to account for all divisors
# Thus, N = 420k + 1 for some integer k
# For N to be a 3-digit number, 100 <= N <= 999

lcm = 2 * 2 * 3 * 5 * 7  # 420
for k in range(1, 3):  # Check k values where 420k + 1 is 3-digit
    N = lcm * k + 1
    if 100 <= N <= 999:
        print(f"N = {N} satisfies N % m = 1 for m = 2, 3, 4, 5, 6, 7")

# Verify manually
N = 421  # Example: k = 1 gives 420 * 1 + 1 = 421
for m in [2, 3, 4, 5, 6, 7]:
    print(f"{N} % {m} = {N % m}")

Prove there exist two integers $n$ with different first digits whose square begins with the digits $31415$. Find such $n$.

A square starts with the prefix $31415$ iff for some integer $t\ge 0$, \(31415\cdot 10^{2t}\ \le\ n^2\ <\ 31416\cdot 10^{2t},\) i.e. \(\sqrt{31415}\cdot 10^{t}\ \le\ n\ <\ \sqrt{31416}\cdot 10^{t}.\) Equivalently, defining the interval \(I=\big[\sqrt{31415},\sqrt{31416}\big)\approx[177.245\ldots,177.271\ldots),\) an integer $n$ works exactly when $n/10^{t}\in I$ for some $t$.

We can choose digits greedily: at each step multiply the current interval by $10$ and select a digit that keeps us inside. Because \(\sqrt{3141.5}=\sqrt{\tfrac{31415}{10}} \approx 56.0490856\ldots,\) both leading digits $1$ and $5$ are possible branches:

1) Branch starting with $1$. Iterating the digit-choosing process yields the unique 6-digit integer \(n=177243,\) and a check shows \(177243^2=31\,415\,081\,049,\) which indeed begins with $31415$.

1) Branch starting with $5$. Continuing the same process produces \(n=560491,\) and \(560491^2=314\,150\,161\,081,\) which also begins with $31415$.

Thus there are at least two such integers with different first digits: \(n=177243 \quad \text{and} \quad n=560491.\)

Integer Linear Combinations - City with 7/13 florins

Imagine a country with 7/13 florins coins. Two people, each has many coins of each type. Can one pay 6 florins to the other?

6 = 13 - 7 what about paying 1 florin? yes: 2 * 7 - 13 = 1 or 7-6=1 what about 2 florins? 4 * 7 - 2 * 13 = 28 - 26 = 2 or 2 * 1 = 2 any (integer) amount is payable

City with 15/21 florins

Now imagine a country with 15/21 coins; how to pay 6?

6 = 21 - 15

What about 8?

Not possible - all payable amounts are multiple of 3 no chances of 1 and 8

What about 3? Possible: 9 = (2 * 15) - 21 6 = 21 - 15 3 = 9 - 6 Thus, 3 and any multiple of 3 is possible.

equation should be 15x+21y=c15, x, plus, 21, y, equals, c if I want to pay c florins.

basically a multiple of the greatest common divisor

a7 + b13 = 5

Quiz:

1. Person A has an unlimited number of 7-florin coins, person B has an unlimited number of 13-florin coins. How A can pay 5 florins to B? A pays 10 florins of 7 and B pays 5 florins of 13 to get 5.
2. A town has three hotels. You have 10 vouchers for one-night stay for the first hotel, 15 for the second one, and 20 for the third one. The rules do not allow you to use vouchers for two consecutive nights in one hotel. Can you use them all for 10 + 15 + 20 = 45 consecutive nights changing the hotels each night?
3. A town has three hotels. You have 10 vouchers for one-night stay for the first hotel, 15 for the second one, and 30 for the third one. The rules do not allow you to use vouchers for two consecutive nights in one hotel. Can you use them all for 10 + 15 + 30 = 55 consecutive nights changing the hotels each night?

Paths in a Graph

So, here is the puzzle. There are three hotels in a town A, B and C and you have vouchers. You have 10 vouchers for hotel A, 15 vouchers for B and 20 for C but there is a restriction. The hotel does not allow you to use the voucher two nights in a row. So you need to change hotels. Every night you should move to a different hotel. The question is whether it is possible to do this for 45 consecutive nights.

Answer: Start with C, keep going from C to B and then when all of them look somewhat equal go from A to B to C.

Repeat a path of length 9 (A = 10/5 = 2, B = 15/5 = 3, C = 20/5 = 4) 5 times. ACACBCBCB [explain this]

If we want to repeat some path several times, the last hotel of the previous iteration and the first hotel of the next iteration should be different

A(10), B(15), C(30) = 55 -> is this possible, no, why?? obstacle: too many vouchers for C

2, 3, 6 ACACBCBCBC -> Only 5 Cs could be fixed not six of them

25, 20, x 5, 4, x

CACACA -> And then I figured basically with every A there can be a C (likewise with every B there can be a C). So, 9x5 is the maximum

You can sleep 46 times in C with one-day breaks, using 20+25=45 other vouchers for the breaks, but not more (not enough to fill all breaks)

Question 3 There are some books on the table. If you group them by 3, you get some number of full groups and 2 books remain; if you group them by 4, you get some number of full groups and 3 books remain; if you group them by 5, you get some number of full groups and 4 books remain. What is the number of books on the table, if it is less than 100? (Maybe Chinese Remainder Theorem)

x%3 = 2 x%4 = 3 x%5 = 4

Dumb way:

for i in range(1, 100):
    if (i % 3 == 2) and (i % 4 == 3) and (i % 5 == 4):
        print(i)

Answer: If you add one book, the number will be a multiple of 2,3,4,5, and these common multiples are multiples of 60.

In some country there are 12-, 20-, and 30-florin coins only. One person in this country wants to pay some amount to other person in this country. What is the minimal amount that can be paid if both people have many coins of each type?

2

12+20-30=2; one cannot pay 1 since all the coins are multiples of 2.

I took out the HCF.