I saw an "If you can solve this you are a genius" puzzle on you YouTube and it goes like this.
"You are given 49 cards numbered 1, 2, 3,..., 49 and the challenge is to put them (not necessarily equally sized) groups so that the sum of the numbers in each group is the same."
The numbers 1 to 50 add up to 1225 and 1225 divided by 7 is 175, so the cards in each group must total 175.
I've seen similar problems before and they are interesting because we can tackle them using a so-called "Greedy algorithm", which roughly speaking works by always grabbing the largest available numbers. There are many situations where a greedy algorithm doesn't work but I believe it always succeeds with the type of problem we are considering here (although I have not been able to prove this is the case.)
It's possible to come up with a computer program to carry out the algorithm but I thought it more interesting to do it manually in a spreadsheet, which shows visually how the algorithm unfolds. Here it is, it's 49 rows long of course but I've done my best to fit it in. My explanation is at the end of the post.
You can see that at each step we gobble up the largest numbers unused at that point until the next largest number wiuld take up past 175. Then we choose the number or numbers that makes the total of the current group up to 175. I have coloured the groups: yellow, blue, green, pink, purple, grey and white. I think I've got the calculations right, I've checked them but it's. a bit fiddly and easy to make a mistake.
I don't for a second suggest this solution is unique, it is just what the greedy algorithm finds, but I expect there will be hundreds or thousands of other ways to solve the puzzle. I think it is probably hard to calculate how many. A simpler question is: how many subsets of 1, 2, 3,..., 49 have a total of 175 and Copilot says 63,019,177 but this is not easy to check.
Greedy Algorithm is Genius!
I saw an "If you can solve this you are a genius" puzzle on you YouTube and it goes like this.
"You are given 49 cards numbered 1, 2, 3,..., 49 and the challenge is to put them (not necessarily equally sized) groups so that the sum of the numbers in each group is the same."
The numbers 1 to 50 add up to 1225 and 1225 divided by 7 is 175, so the cards in each group must total 175.
I've seen similar problems before and they are interesting because we can tackle them using a so-called "Greedy algorithm", which roughly speaking works by always grabbing the largest available numbers. There are many situations where a greedy algorithm doesn't work but I believe it always succeeds with the type of problem we are considering here (although I have not been able to prove this is the case.)
It's possible to come up with a computer program to carry out the algorithm but I thought it more interesting to do it manually in a spreadsheet, which shows visually how the algorithm unfolds. Here it is, it's 49 rows long of course but I've done my best to fit it in. My explanation is at the end of the post.
You can see that at each step we gobble up the largest numbers unused at that point until the next largest number wiuld take up past 175. Then we choose the number or numbers that makes the total of the current group up to 175. I have coloured the groups: yellow, blue, green, pink, purple, grey and white. I think I've got the calculations right, I've checked them but it's. a bit fiddly and easy to make a mistake.
I don't for a second suggest this solution is unique, it is just what the greedy algorithm finds, but I expect there will be hundreds or thousands of other ways to solve the puzzle. I think it is probably hard to calculate how many. A simpler question is: how many subsets of 1, 2, 3,..., 49 have a total of 175 and Copilot says 63,019,177 but this is not easy to check.