Maths
Tagged: #Question
- This topic has 15 replies, 12 voices, and was last updated 2 weeks, 2 days ago by frazza238.
-
AuthorPosts
-
10th September 2024 at 12:07 pm #93739HarryKeymaster
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!
8th October 2024 at 10:52 am #96311molleculeYTParticipantThe 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
14th October 2024 at 9:46 am #97270ByteInBitsParticipantA 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 = DFind A, B, C, and D
Can you solve it quickly?
15th October 2024 at 6:14 pm #97505RickOSheaParticipantPart 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
16th October 2024 at 11:00 pm #97445CaldewBA-AlfieParticipantHere’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)21st October 2024 at 7:15 am #97544AstralicaParticipantKeep everything a knight’s move apart. One solution would be to have the coins on a8, b4, c7, d3, e6, f2, g5 and h1.
23rd October 2024 at 3:28 pm #97860USB-C_is_supremeParticipantHi 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
24th October 2024 at 11:49 am #97920RickOSheaParticipantRegarding 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_24th October 2024 at 4:23 pm #97938AstralicaParticipant@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
24th October 2024 at 6:18 pm #97947RickOSheaParticipantThat 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 49Obviously I want to maintain symmetry, but avoid collisions for different arrangements. Do you have any thoughts?
Thanks
24th October 2024 at 7:24 pm #97943AstralicaParticipant@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 = 324th October 2024 at 7:26 pm #97950AstralicaParticipant@USB-C_is_supreme
Here’s a proof my friend Indigo_Cerulean made:
It proves those four solutions are the only possible ones.
24th October 2024 at 7:28 pm #97951AstralicaParticipant@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.
24th October 2024 at 10:11 pm #97968ByteInBitsParticipantI 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^n25th October 2024 at 10:04 am #97970KyleParticipantI 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
-
AuthorPosts
- You must be logged in to reply to this topic.