Posts

practice problems pending

Image
Q1)   A square of dimension (n-1) * (n-1) is divided into (n-1)^2 unit squares in the chess board manner. Now, each of these (n^2) vertices of these squares are to be painted black or blue such that each unit square has exactly two black vertices. In how many ways can this be done? S1. Look at an individual square. There are 2 ways for it to yield 2 black vertices. One horizontal edge blue(or black), other black(or blue). Or 1 color each on top edge, and similarly on bottom edge. Once you expand the pattern, there will be only 2 ways to get it done. Each row alternates or each column alternates or both alternate. Case 1: Each row alternates. So each row can start with one of 2 colors and then the pattern is fixed. So 2^n ways since there are 'n' rows. Case 2: Each column alternates. 2^n again. Case 3: Both alternate. Exactly 2 ways like a chessboard. Total: 2^n.2 - 2 = 2^(n+1) - 2. Q2. S2. As the diagram shows a 2x2 bounding box can hold 2 different squares. That rule actually ...
Post a Comment
Read more

Fermat's Theorem on Sums of Two Squares

 If an odd prime number leaves remainder of 1 when divided by 4 then it can be expressed as sum of two integer squares and those 2 integers will be unique for this prime. Examples:  17 = 16 + 1 29 = 25 + 5 41 = 25 + 16 1013 = 22^2 + 23^2
Post a Comment
Read more

practice problems

Q1.  Find the number of triangles whose angular points are at the angular points of a given polygon of (n) sides, but none of its sides are the sides of the polygon. S1. Simple application of  Kaplansky's first lemma . Formula derived is: (n-k-1)C(k-1) + (n-k)C(k) Here k = 3 (n-4)C(2) + (n-3)C(3) = (n-4)(n-5)/2 + (n-3)(n-4)(n-5)/6 = (n-4)(n-5)/2[1 + (n-3)/3] = n(n-4)(n-5)/6
Post a Comment
Read more

number 2026 properties

1. Is 2026 a semiprime(product of only 2 primes)? Yes 2. Is 2026 a deficient number(sum of its proper divisors is less than the number itself)? Yes 3. Is it a happy number? If you keep squaring the digits and adding and then repeating - does it reduce to 1? Yes 4. Is it sum of 2 squares? 45^2 + 1^2 5. Is 1013 sum of 2 squares? = 22^2 + 23^2 ( Fermat theorem on sum of 2 squares )
Post a Comment
Read more

practice problems

Q1. (n) is a positive integer. (A) is a set such that A={1,2,...,n}. Let (t_n) denote the number of subsets of (A) such that the arithmetic mean (AM) of the elements is an integer. Prove that (t_n) and (n) are both odd or both even. S1. 1. Let us ignore empty subset since A.M. is not defined for that. 2. Subsets of size 1: {1}, {2} ... {n}. There are 'n' such subsets. And each of them has their A.M. as integer. 3. Now let's consider the subsets with size >= 2 which have an integer A.M. Let G be the set of all such subsets. Let's consider a function 'f' defined for subsets of size >= 2. f(S) = S - {k} where k is the A.M. of S and k is present in S. f(S) = S + {k} where k is the A.M. of S and k is not present in S. For e.g. S = {1,3,8}, k = (1+3+8)/3 = 4 4 is not there in S. f(S) = {1,3,4,8} S = {1,2,3}, k = (1+2+3)/2 = 3 3 is there in S. f(S) = {1,2} Note 1: S and f(S) have the same A.M. Why? Let S = {a1,a2...,ak} AM = sigma(a_i)/k If you remove AM, the ne...
Post a Comment
Read more

practice problems

Q1. Find integer solutions for x^2 + y^2 = 2025 S1. Mod 9 of a square gives 0,1,4,7 Here RHS is 0. For LHS to be 0, both have to give mod 0. => x = 3a, y = 3b => a^2 + b^2 = 225 Again mod 9 is 0 a = 3c, b = 3d c^2 + d^2 = 25 (c,d) = (0,+-5) (-+5,0) (-+3,-+4) (-+4,-+3) Total solutions = 2 + 2 + 4 + 4 = 12 To find actual solutions multiply c,d with 9.
Post a Comment
Read more

diophantine equations theory

Theorem: If a1x1 + a2x2 + .... an.xn = K then this Diophantine equation has a solution if d | K where d = gcd(a1,a2...an). We can note the similarities with Bezout's lemma here. Practice: Which of these Diophantine equations have integer solutions? 1. 21x + 15y = 17 2. 7x + 17y = 27 Theorem: If ax + by = c and d | c, where d = gcd(a,b), then this Diophantine equation has infinitely many solutions, and the solutions are of the form x = x0 + (b/d).k, y = y0 - (a/d).k, where k is integer and (x_0, y_0) are particular solutions of (ax + by = c); and x0, y0 are integers.
Post a Comment
Read more