Sunday Times Teaser 3131 – Heads Up Savings

by BRG on September 23, 2022

by Howard Williams

Published Sunday September 25 2022 (link)

Little Spencer saves 5p coins in a jar, and when they reach £10, deposits them in his savings account. He likes playing with the coins. In one game, after first turning them all heads up, he places them in a row on the table. Starting from the left, he then turns over every 2nd coin until he has reached the end of the row. He then again starts from the left, and this time turns over every 3rd coin. He repeats this for every 4th, 5th coin etc, until finally he turned over just one coin, the last in the row.

At the end of the game I could see that if Spencer had exactly 75 per cent more coins he would have an increase of 40 per cent in the number showing heads. However, if he had exactly 50 per cent fewer coins, he would have a decrease of 40 per cent in the number showing heads.

What is the value of his 5p savings?

From → Uncategorized

4 Comments Leave one →

Brian Gladman permalink

If we number the coins from 1 upwards, a coin at position N (> 1) will be turned over once for each divisor of N greater than 1. And, since non-square / square numbers have odd / even numbers of divisors, the game will finish with only the coins at square positions showing heads. This hence provides a faster way of counting the number of heads showing after each game.


shortcut = False

if shortcut:
  from math import isqrt as play
else:
  from itertools import accumulate
  # play the game with <n> coins, return 
  # the number of heads remaining
  coins = [1] * 200
  for i in range(2, 201):
    for j in range(i, 201, i):
      coins[j - 1] ^= 1
  cs = list(accumulate(coins))
  play = lambda nc: cs[nc]

# for 40%, 100% and 175% of the coins to be integer,
# the number of coins must be  multiple of four
for nc in range(4, 200, 4):
  nh = play(nc)
  # a 50% decrease in coins gives a 40% decrease in heads 
  if 5 * play(nc // 2) == 3 * nh:
    # a 75% increase in coins gives 40% increase in heads
    if 5 * play(nc * 7 // 4) == 7 * nh:
      print(f"£{5 * nc / 100:.2f}")

shortcut = False

if shortcut:

from math import isqrt as play

else:

from itertools import accumulate

# play the game with <n> coins, return

# the number of heads remaining

coins = [1] * 200

for i in range(2, 201):

for j in range(i, 201, i):

coins[j - 1] ^= 1

cs = list(accumulate(coins))

play = lambda nc: cs[nc]

# for 40%, 100% and 175% of the coins to be integer,

# the number of coins must be multiple of four

for nc in range(4, 200, 4):

nh = play(nc)

# a 50% decrease in coins gives a 40% decrease in heads

if 5 * play(nc // 2) == 3 * nh:

# a 75% increase in coins gives 40% increase in heads

if 5 * play(nc * 7 // 4) == 7 * nh:

print(f"£{5 * nc / 100:.2f}")

Frits permalink

Similar.

Doing the 50% decrease check first seems to be more efficient.


# play the flip game and return the number of showing heads
def nr_heads(n):
  s = [1] * n
  for i in range(2, n + 1):
    # flip all coins on places which are multiples of <i>
    for j in range(i, n + 1, i):
      s[j - 1] = 1 - s[j - 1]
  return sum(s)

d = dict()

# little Spencer's number of coins must be a multiple of 4 and ...
for n in range(4, 200, 4):
  d[n] = nr_heads(n)
  # ... his number of heads showing must be a multiple of 5
  if d[n] % 5: continue

  # 50 per cent fewer coins: he would have a decrease of 40 per cent
  m = n // 2
  fewer = d[m] if m in d else nr_heads(m)
  if 5 * fewer != 3 * d[n]: continue

  # 75 per cent more coins: he would have an increase of 40 per cent
  m = n * 7 // 4
  more = nr_heads(m)
  if 7 * d[n] != 5 * more: continue
  print("the value of his savings =", str(5 * n) + "p")

# play the flip game and return the number of showing heads

def nr_heads(n):

s = [1] * n

for i in range(2, n + 1):

# flip all coins on places which are multiples of <i>

for j in range(i, n + 1, i):

s[j - 1] = 1 - s[j - 1]

return sum(s)

d = dict()

# little Spencer's number of coins must be a multiple of 4 and ...

for n in range(4, 200, 4):

d[n] = nr_heads(n)

# ... his number of heads showing must be a multiple of 5

if d[n] % 5: continue

# 50 per cent fewer coins: he would have a decrease of 40 per cent

m = n // 2

fewer = d[m] if m in d else nr_heads(m)

if 5 * fewer != 3 * d[n]: continue

# 75 per cent more coins: he would have an increase of 40 per cent

m = n * 7 // 4

more = nr_heads(m)

if 7 * d[n] != 5 * more: continue

print("the value of his savings =", str(5 * n) + "p")

John Z permalink


from number_theory import divisors

# ht : heads(1) or tails(0)
# the number of divisors a coin position has is the number of 'flips' - 1
ht = tuple(len(divisors(n)) % 2 for n in range(200))

# consider number of coins
for nc in range(4, 114, 4):
  # number of heads for number of coins
  nh = ht[:nc + 1].count(1)

  # number of heads for 75% more coins
  nh75 = ht[:nc * 7 // 4 + 1].count(1)

  # number of heads for 50% fewer coins
  nh50 = ht[:nc // 2 + 1].count(1)

  if nh75 / nh == 1.4 and nh50 / nh == 0.6:
    print(f'{nc} coins worth £{nc * 5 / 100:.2f};',
          f'number of heads: {nh, nh75, nh50}')

from number_theory import divisors

# ht : heads(1) or tails(0)

# the number of divisors a coin position has is the number of 'flips' - 1

ht = tuple(len(divisors(n)) % 2 for n in range(200))

# consider number of coins

for nc in range(4, 114, 4):

# number of heads for number of coins

nh = ht[:nc + 1].count(1)

# number of heads for 75% more coins

nh75 = ht[:nc * 7 // 4 + 1].count(1)

# number of heads for 50% fewer coins

nh50 = ht[:nc // 2 + 1].count(1)

if nh75 / nh == 1.4 and nh50 / nh == 0.6:

print(f'{nc} coins worth £{nc * 5 / 100:.2f};',

f'number of heads: {nh, nh75, nh50}')

John Z permalink

Based on Brian’s observation that square numbers have an even number of divisors and non square numbers have an odd number of divisors…


# squares up to 200
sq = tuple(i * i for i in range(1, 15))

# ht : heads(1) or tails(0)
# the number of divisors a coin position has is the number of 'flips' - 1
# number of divisors is even for perfect squares, odd (i. e. tails) otherwise
ht = tuple(1 if n in sq else 0 for n in range(200))

# consider number of coins; must be divisible by 4
for nc in range(4, 114, 4):
  # number of heads for number of coins
  nh = ht[:nc + 1].count(1)

  # number of heads for 75% more coins
  nh75 = ht[:nc * 7 // 4 + 1].count(1)

  # number of heads for 50% fewer coins
  nh50 = ht[:nc // 2 + 1].count(1)

  if nh75 * 5 == nh * 7 and nh50 * 5 == nh * 3:
    print(f'{nc} coins worth £{nc * 5 / 100:.2f};',
          f'number of heads: {nh, nh75, nh50}')

# squares up to 200

sq = tuple(i * i for i in range(1, 15))

# ht : heads(1) or tails(0)

# the number of divisors a coin position has is the number of 'flips' - 1

# number of divisors is even for perfect squares, odd (i. e. tails) otherwise

ht = tuple(1 if n in sq else 0 for n in range(200))

# consider number of coins; must be divisible by 4

for nc in range(4, 114, 4):

# number of heads for number of coins

nh = ht[:nc + 1].count(1)

# number of heads for 75% more coins

nh75 = ht[:nc * 7 // 4 + 1].count(1)

# number of heads for 50% fewer coins

nh50 = ht[:nc // 2 + 1].count(1)

if nh75 * 5 == nh * 7 and nh50 * 5 == nh * 3:

print(f'{nc} coins worth £{nc * 5 / 100:.2f};',

f'number of heads: {nh, nh75, nh50}')

Sunday Times Teaser 3131 – Heads Up Savings

by Howard Williams

Published Sunday September 25 2022 (link)

Leave a comment to John Z Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta