Skip to content

Instantly share code, notes, and snippets.

@nileshtrivedi
Created June 25, 2022 12:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nileshtrivedi/6380bf6fd38efd45bbb8f409d4252c25 to your computer and use it in GitHub Desktop.
Save nileshtrivedi/6380bf6fd38efd45bbb8f409d4252c25 to your computer and use it in GitHub Desktop.
"I don't know the numbers": a math puzzle
# My solution to a cool math puzzle
# Two numbers are chosen randomly, both are positive integers smaller than 100. Sandy is told
# the sum of the numbers, while Peter is told the product of the numbers.
# Then, this dialog occurs between Sandy and Peter:
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I don’t know the numbers.
# Sandy: I don’t know the numbers.
# Peter: I do know the numbers.
# What are the numbers?
sum_map = {}
product_map = {}
(1..99).to_a.each do |a|
(a..99).to_a.each do |b|
sum_map[a+b] ||= []
sum_map[a+b] << [a,b]
product_map[a*b] ||= []
product_map[a*b] << [a,b]
end
end
7.times do
# Peter says I don't know
# Which means Product is a number which has multiple factorizations
# We can delete from map those with unique factorization
product_map.select { |k,v| v.size == 1 }.each do |product,v|
f = v.first # cannot be a candidate
product_map = product_map.except(product)
# the pair f is not a valid candidate so should be removed from a+b's possible partitions
sum_map[f.first + f.last].reject! { |p| p == f}
sum_map.reject! { |p| p == (f.first + f.last) && sum_map[f.first + f.last].empty? }
end
# Sandy says I don't know
# Which means Sum is a number which has multiple partitions
# We can delete from map those with unique partition
sum_map.select { |k,v| v.size == 1 }.each do |sum,v|
pt = v.first # cannot be a candidate
sum_map = sum_map.except(sum)
# the pair pt is not a valid candidate so should be removed from a+b's possible partitions
product_map[pt.first * pt.last].reject! { |f| f == pt}
product_map.reject! { |p| p == (pt.first * pt.last) && product_map[pt.first * pt.last].empty? }
end
end
puts product_map.select { |k,v| v.size == 1 }.first.last
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment