Number Theory, Division, Parity (Even/Odd)

Parity refers to whether an integer is even (divisible by 2) or odd (not divisible by 2). Many problems, especially in number theory and combinatorics, can be solved or simplified by considering the parity of the numbers involved. Questions often require analyzing how operations affect parity.

• Question

  Does there exist a perfect square whose digits sum to `2001`?

  Justify or provide an example!

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Prime Numbers -> Prime Factorization Proof and Example -> Proof by Contradiction
  Sources:
  • problems.ru web site

• Ali Baba and the Forty Thieves

  Ali Baba wrote the number `17` on a piece of paper. The forty thieves pass the paper to each other, and each one either adds `1` to the existing number, or subtracts `1`, until each of them has done so once, and then they return the paper to Ali Baba.

  Is it possible that the number now written on the paper is `40`?

  Topics:

  Arithmetic Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  Is it possible for the sum of three natural numbers to be divisible by each of them?

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample
  Sources:
  • problems.ru web site

• Question

  Find all pairs of prime numbers whose difference is `17`.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  Prove that the product of three consecutive numbers is divisible by `6`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Prime Numbers -> Prime Factorization

• Question

  Prove that for every prime number `p>3 ` the following holds: `p^2-1` is divisible by `6`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Algebra -> Algebraic Techniques -> Short Multiplication Formulas / Algebraic Identities Number Theory -> Division -> Parity (Even/Odd) Proof and Example Number Theory -> Prime Numbers -> Prime Factorization

• Question

  A knight exited the square `a1` and, after several moves, returned to the same square.

  Is it possible that the knight made an odd number of moves?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Colorings -> Chessboard Coloring

• Question

  A knight moves from square `a1` to square `h8`. Is it possible that along the way it visited every square on the board exactly once?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Combinatorics -> Invariants Combinatorics -> Graph Theory Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Every person who ever lived on Earth performed a certain number of handshakes (including 0). Prove that the number of people who performed an odd number of handshakes is even.

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  The magical land consists of `25` provinces. Is it possible that each province borders an odd number of other provinces?

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings