Tagged: by: M. C. Moore Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:39 am on 3 January 2021 Permalink | Reply
    Tags: by: M. C. Moore   

    Brain-Teaser 17: [Knight’s tour] 

    From The Sunday Times, 25th June 1961 [link]

    In “Amusements in Mathematics” (Nelson, 1917), the late Henry Ernest Dudeney published a magic knight’s tour of the chessboard. That is to say, a knight placed on the square numbered 1 could, by ordinary knight’s moves, visit every square of the board in the ordered numbered, and the numbers themselves in each row and column added up to 260. Yet it was not a fully magic square, for the diagonals did not add to the same constant. After much trying Dudeney came to the conclusion that it is not possible to devise such a square complete with magic diagonals, but, as he said, a pious opinion is not a proof.

    You are invited to try your skill in devising a magic knight’s tour of a square 7×7, with or without magic diagonals.

    Dudeney’s Amusements in Mathematics is available on Project Gutenberg [link].

    This puzzle was originally published with no title.

    [teaser17]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 3 January 2021 Permalink | Reply

      A 7×7 chessboard has 49 squares. So if we colour the corners black there will be 25 black squares and only 24 white squares. So the knight will have to start on a black square, and end on a black square. (So it is not possible for a tour to form a closed loop).

      So, 1 is on a black square. The next square in the tour will be a white square (as a knight always moves to a square of the other colour). So, 2 will be on a white square, 3 on a black square, etc. When the tour is complete all the black squares will be odd numbers and all the white squares will be even numbers.

      The rows/columns alternate between (4 black + 3 white) and (4 white + 3 black) squares, but the total of a row/column consisting of (4 black + 3 white) numbers will be (4 odd + 3 even) = even. And the total of a row/column consisting of (4 white + 3 black) will be (4 even + 3 odd) = odd. And we require the sum of each row and column to be the same (it should be T(49) / 7 = 175),

      So it will not be possible for us to make a magic squares as the sums of the values in the rows and columns will necessarily alternate between even and odd, so they can’t all be the same.

      Hence it is not possible to construct a magic knight’s tour on a 7×7 board.

      Like

    • Hugh Casement's avatar

      Hugh Casement 1:35 pm on 3 January 2021 Permalink | Reply

      Dudeney was by no means the first: see
      https://www.mayhematics.com/t/1d.htm
      https://mathworld.wolfram.com/MagicTour.html

      It has been proved (by computer) to be impossible on an 8×8 board,
      though there are many semi-magic tours.

      Like

  • Unknown's avatar

    Jim Randell 10:34 am on 18 October 2020 Permalink | Reply
    Tags: by: M. C. Moore   

    Brain-Teaser 11: Circulation poor 

    From The Sunday Times, 7th May 1961 [link]

    Lazy Jack was engaged to deliver a circular to every house in the district. He found the supply of circulars would divide into fourteen equal batches of rather more than 300 each, so he decided to deliver one batch each day and thus spread the job over a fortnight.

    On the first day he faithfully distributed circulars one to a house, but that proved very tiring, so the next day he delivered two at each house he visited. With a fine sense of fairness, he never delivered to the same house twice, and one each succeeding day he chose the next smaller number of houses to visit that would enable him exactly to exhaust the day’s batch by delivering an equal number of circulars at each house. The fourteenth day’s batch of circulars all went through one letter box.

    To how many houses was delivery made?

    [teaser11]

     
    • Jim Randell's avatar

      Jim Randell 10:35 am on 18 October 2020 Permalink | Reply

      On each of 14 days, Jack delivers n leaflets:

      On the first day 1 leaflet to each of n houses.
      On the second day 2 leaflets to each of(n / 2) houses.
      …
      On the 14th day n leaflets to 1 house.

      So we are looking for n, an even number, greater than 300, with exactly 14 divisors.

      We can then calculate the total number of houses visited by determining the sum of the divisors.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import (irange, inf, divisors, printf)

for n in irange(302, inf, step=2):
  ds = divisors(n)
  if len(ds) == 14:
    t = sum(ds)
    printf("t={t} [n={n} ds={ds}]")
    break

      Solution: Delivery was made to 762 houses.

      And there were 14×320 = 4480 leaflets to deliver.

      We can find numbers with exactly k divisors by considering factorisations of k (see: Enigma 1226).

      In this case, 14 = 1 × 14 = 2 × 7, so any number of the form:

      n = p^13
      n = p^1 × q^6

      for primes, p and q, will have exactly 14 divisors. [*]

      And we know one of the primes is 2.

      2^13 = 8192, which is too big.

      So we know: n = p × q^6.

      If p = 2, then the smallest possible values for n is 2 × 3^6 = 1458, which is also too big.

      So q = 2, and possible values for n are:

      3 × 2^6 = 192
      5 × 2^6 = 320
      7 × 2^6 = 448
      …

      The only sensible candidate is: n = 320, the 14 divisors are:

      1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 160, 320

      and their sum is 762.

      The sum can also be worked out directly from the prime factorisation of n:

      If σ(n) = the sum of the divisors of n, we have:

      σ(5 × 2^6) = σ(5) × σ(2^6)
      = (1 + 5) × (2^7 − 1)
      = 6 × 127
      = 762

      [*] In the published solution it is claimed that only numbers of the form (p^6 × q) have exactly 14 divisors.

      Like

    • Frits's avatar

      Frits 10:28 pm on 18 October 2020 Permalink | Reply

      Only to check if I could solve it with [[SubstitutedExpression]] without using external functions.

      from enigma import  SubstitutedExpression

p = SubstitutedExpression([
    # Consider first 7 divisors (1, 2, .....)
    "XYZ > 300",
    "XYZ % 2 == 0",   # as specified
    "XYZ % IJ == 0",  # 7th divisor
    "XYZ % GH == 0",  # 6th divisor
    "XYZ % EF == 0",  # 5th divisor
    "XYZ % CD == 0",  # 4th divisor
    "XYZ % AB == 0",  # 3rd divisor
    # put them in order
    "GH < IJ",
    "EF < GH",
    "CD < EF", 
    "AB < CD", 
    "2 < AB ",
    # limit 7th divisor 
    "IJ < (XYZ // IJ)",
    # make sure there are only 7 divisors before 8th divisor
    "sum(1 for x in range(1, (XYZ // IJ)) if XYZ % x == 0) == 7",
    ],
    verbose=0,
    d2i={k:"X" for k in [x for x in range(0,10) if x != 3]},
    #accumulate=min,
    answer="(1, 2, AB, CD, EF, GH, IJ, XYZ)",
    distinct="",
    #reorder=0
)

# Solve and print answers

for (_, ans) in p.solve():
 hs = 0
 # sum the divisors
 for i in range(0,7):
   hs += ans[i] + ans[7]//ans[i]
 print(f"{hs} houses")

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started