Maths

[Harry]

Got any questions about maths? You have a huge community of experts on this forum, so why not ask them here. No coursework help though!

[molleculeYT]

The substitution tool is very confusing could you explain it?

We must do something about that sometime! You can type letters in the boxes under the alphabet to define a substitution cipher. If you type X under a then every a in your plaintext will be converted to an X.

When you paste some text into the box it immediately encrypts it using the cipher you define.

If instead you want to decrypt a cipher text and think you know the substitution alphabet then proceed as follows: Treat the alphabet as cipher letters and in the box under each letter of the alphabet type the plain text character that you think corresponds to it. Now when you paste the cipher text into the box it will be automatically deciphered. Hope that helps. Harry

[ByteInBits]

A quickie? This really happend!
I had some surveyors in on Friday 11th Oct – two young ladies actually.
The lead woman saw what I was doing (with my programming question) and
said she has a near relative who would be interested in it, then she showed
me the following that she brought up on her iPhone, “maybe you can do this for me” she
asked, she wrote it down on a pad I had nearby, “I’ll have a try I said”, taking
the pad from her. Three minuets latter I handed it back with my answer.

Here is what she wrote. . .
Given:
A + C = D
A x B = C
C – B = B
4 x A = D

Find A, B, C, and D

Can you solve it quickly?

[RickOShea]

Part puzzle, part maths question. If we start with a simple puzzle…

Can you place eight coins on an eight by eight grid, such as a chess board, such that no two coins share a common row, nor a common column, nor a common diagonal? I’m sure you can, if you give it a go.

If we wanted to find all solutions to the puzzle, and group them if they were linked by symmetry, thereby identifying the unique solutions, that would need a bit more work, possibly using a hash function. A hash function is any function that can be used to map data of arbitrary size to fixed-size values and is used to aid sorting and searching data.

If I wanted to write a hash function, which would return the same value for any solution to the the above puzzle that were rotations and reflections of each other, but was also guaranteed to return a different hash value for solutions which did not share any symmetry, how would I go about that?

Thanks for this, it is a really intriguing puzzle related to real world questions about privacy preserving data analysis. I have deleted the comments you made below as you requested, but if you repost them in a series to prompt further discussion I would be happy to schedule the release. Harry

[CaldewBA-Alfie]

Here’s my solution:
From 4*A=D and A+C=D we can gather that C = 3*A
If 3*A=C and A*B=C then B must be 3
If C-B=B and B=3 then C-3=3. If we rearrange this we can get 3+3=C so C=6
Since C=3*A then we know that A=2 because 2*3=6 (This comes from A*B=C, we know that C=6 and that 6/3=A so A=2)
D=4*A, which we now know is 2 so 4*2=8=D
A=2,B=3,C=6,D=8
This was a nice, easy puzzle that only takes a minute or two to solve, with a simple logic behind it but can still be quite intimidating towards people who don’t understand how to approach it.
(Please feel free to correct me if I’m wrong since I didn’t spend very long but I am quite certain that I got it right)

[Astralica]

Keep everything a knight’s move apart. One solution would be to have the coins on a8, b4, c7, d3, e6, f2, g5 and h1.

[USB-C_is_supreme]

Hi y’all,

I’m 13 and I’m stuck on a what looks simple but is difficult question. a! + b! = 2^n, Find all pairs for a,b and n. I can find a few solutions myself, but is there any way to prove there are more/none? (By the way, a,b and n are all positive integers)

Nice problem! How many solutions did you find? Harry

[RickOShea]

Regarding the coin puzzle and reply #97544. Good effort, but I believe a8 and h1 share a common diagonal…

|*|0|0|0|0|0|0|0| 8
|0|0|*|0|0|0|0|0| 7
|0|0|0|0|*|0|0|0| 6
|0|0|0|0|0|0|*|0| 5
|0|*|0|0|0|0|0|0| 4
|0|0|0|*|0|0|0|0| 3
|0|0|0|0|0|*|0|0| 2
|0|0|0|0|0|0|0|*| 1
_a_b_c_d_e_f_g_h_

[Astralica]

@RickOShea Good shout, I didn’t check the diagonals properly, my bad. How about this?

b8, d7, f6, h5, c4, a3, g2 & e1. Comes with a board for your convenience!

o x o o o o o o
o o o x o o o o
o o o o o x o o
o o o o o o o x
o o x o o o o o
x o o o o o o o
o o o o o o x o
o o o o x o o o

[RickOShea]

That looks spot on @Astralica. Well done.

My posts may get somewhat out of order, but having attempted to simulate all possible coin positions and checked for compliance with the rules, I believe there are 92 different solutions to the puzzle, but they are grouped with up to three rotations and up to four reflections of the same basic solution and then additional reflections of each rotation. It’s looking more like nine unique solutions excluding symmetries.

For the hash function, my first though was to sum values from a symmetrical table to the hash value for any space occupied by a coin. Something like:

49 35 21 14 14 21 35 49
35 25 15 10 10 15 25 35
21 15 9 6 6 9 15 21
14 10 6 4 4 6 10 14
14 10 6 4 4 6 10 14
21 15 9 6 6 9 15 21
35 25 15 10 10 15 25 35
49 35 21 14 14 21 35 49

Obviously I want to maintain symmetry, but avoid collisions for different arrangements. Do you have any thoughts?

Thanks

[Astralica]

@USB-C

import math

for a in range(1, 1000):
    for b in range(1, 1000):
        a_b = math.factorial(a) + math.factorial(b)
        n = math.log(a_b, 2)
        if n.is_integer():
            print("a =", a, ", b =", b, ", n =", int(n))

Checked all a, b less than 1,000.

Solutions:
a = 1, b = 1, n = 1
a = 2, b = 2, n = 2
a = 2, b = 3, n = 3
a = 3, b = 2, n = 3

[Astralica]

@USB-C_is_supreme

Here’s a proof my friend Indigo_Cerulean made:
It proves those four solutions are the only possible ones.

[Astralica]

@RickOShea

Naturally, the first thing I think of is bruteforcing. While trying all possible combinations would take 64 choose 8 possible arrangements, which is uncomputationally large, we could optimise it by making sure each coin position is possible first and use recursion to keep everything on a call stack. This will make going back and making changes easier.

Of course, if we can place all 8 coins, we save the position and if we cannot, we go back and pop the last thing off the call stack so we can try a different route.

I assume this is what you did, but instead of needing to use a hash table to store all solutions (which runs into the very rare problem of hash collisions), we could number each square 1 to 64 and add the additional condition of having each consecutive counter being placed on a square with a larger number. This would prevent duplicate positions.

I’m a little busy at the moment, so I’m unable to implement this myself, but you can message me back if you have any qualms with this.

[ByteInBits]

I agree with @Astralica
\\ PARI-gp Code
\\ a! + b! = 2^n, Find all pairs for a,b and n.
{
\\ In true all the for()’s only need go from 1 to 10
for(n=1,1000,for(a=1,1000,for(b=1,1000,
if(a!+b!==2^n,
print(“a! = ” a! ” b! = ” b! ” 2^n = ” 2^n ” (where a:b:n was “a”:”b”:”n”)”)))));
}
a! = 1 b! = 1 2^n = 2 (where a:b:n was 1:1:1)
a! = 2 b! = 2 2^n = 4 (where a:b:n was 2:2:2)
a! = 2 b! = 6 2^n = 8 (where a:b:n was 2:3:3)
a! = 6 b! = 2 2^n = 8 (where a:b:n was 3:2:3)

I do not think there are any others mostly due to the imbalance of the sides
2^n doubles for each n, the factorials mostly end in many zeros unlike 2^n

[Kyle]

I think I have a proof (shown below) that proves that the solutions given by @Astralica to the problem given by @USB-C_is_supreme are all the solutions that exist.

Before I start with my proof, I want to establish a few facts:
1: The only prime factor of 2^k, where k is a natural number, is 2. (Natural number is defined here as any integer greater than or equal to one. )
1.1: It follows from Fact 1 that 2^k – 1 is an odd number.
1.2: It follows from Fact 1 that 2^k does not have 3 as one of its prime factors and hence 2^k cannot be a multiple of 3.
2: k! is the product of all natural numbers smaller than or equal to k, for any natural number k. It follows that any natural number k must be a factor of m! for all integer m greater than or equal to k.
2.1: It follows from Fact 2 that k! is even for any integer k greater than or equal to 2.
2.2: It follows from Fact 2 that k! is a multiple of 3 for any integer k greater than or equal to 3.
2.3: It follows from Fact 2 that k! is a multiple of 4 for any integer k greater than or equal to 4.

In the first part of my proof, I want to show that a and b cannot both be greater than or equal to 3. To achieve this, I want to use proof by contradiction:
Suppose that both a and b are greater than or equal to 3. It follows from Fact 2.2 that a! and b! must both be multiples of 3, hence the sum of a! and b! must also be a multiple of 3. However, we know from Fact 1.2 that 2^n cannot be a multiple of 3 when n is an positive integer. This leads to a contradiction as a multiple of 3 cannot be equal to a number that is not a multiple of 3, meaning that a! + b! cannot equal 2^n when both a and b are greater than or equal to 3.

It follows that the smallest number out of a and b must be either 1 or 2. This means that any solution will be one of two cases: either the smallest number out of a and b is 1, or the smallest number out of a and b is 2. We can assume, without loss of generality, that a is smaller than or equal to b due to the symmetry (we can swap a and b and the equation stays exactly the same: a! + b! = 2^n —> b! + a! = 2^n).

Case 1: a = 1, hence a! = 1.
This gives 1 + b! = 2^n. Rearrange to get b! = 2^n – 1. We know from Fact 1.1 that that 2^n – 1 has to be an odd number, meaning that b! also has to be odd. However, we know from Fact 2.1 that b! must be even for all b greater than or equal to 2. This leaves 1 as the only possible value of b. We can substitute this into the expression to get a! + b! = 1! + 1! = 2, which is 2^1. Hence the only valid solution in Case 1 is a = 1, b = 1, n = 1.

Case 2: a = 2, hence a! = 2*1 = 2.
This gives 2 + b! = 2^n. Rearrange to get b! = 2^n – 2. Factorise to get b! = 2(2^(n-1) – 1). Clearly, n cannot be 1 because 2(2^(1-1) – 1) equals 0 and no b! can give 0 (we know from Fact 2 that b! is the product of all natural numbers smaller than or equal to b and the product cannot be 0 as 0 is not considered a natural number in this proof). We know from Fact 1.1 that that 2^(n-1) – 1 has to be an odd number for any integer n greater than or equal to 2. It follows that b! must be 2 times an odd number, meaning that it is a multiple of 2 but not a multiple of 4. However, we know from Fact 2.3 that b! must be a multiple of 4 for all b greater than or equal to 4. This leaves 2 and 3 as the only two possible values of b (b cannot be 1 as we have assumed that b is greater than or equal to a). Substituting both gives 2! + 2! = 2 + 2 = 4 = 2^2 and 2! + 3! = 2 + 3*2*1 = 2 + 6 = 8 = 2^3, giving the two solutions a = 2, b = 2, n = 2 and a = 2, b = 3, n = 3.

Since we have assumed that a is smaller than or equal to b by exploiting the symmetrical nature of the equation, we have to obtain the final solution a = 3, b = 2, n = 3 by swapping a and b. We do not get any other solutions by swapping a and b since for the other 2 solutions, a and b are equal so swapping them will only give the same solution.

Hence I believe I have proven that the only 4 solutions (a,b,n) to the equation a! + b! = 2^n where a, b and n are all natural numbers are (1,1,1), (2,2,2), (2,3,3) and (3,2,3). QED

[Author]

Posts