Math professor giving $100 for puzzle

[Chronoshock]

Here's how it works, in the beginning of class our prof gave us all an index card and had us write out a "random" 25 digit number. He then collected the cards and said that there were two subsets of those 90 numbers that came to the same sum (ex: 1st number + 4th number + 18 number = 3rd number + 87th number). The challenge is to find one such matching.

For those wondering:
This is true for ANY set of 90 25-digit numbers by the Pigeonhole principle--there are 2^90 (around 1.something * 10^27) possible subsets and less than 90*10^25 values (.9 * 10^27).

Here's the list of the numbers:
http://theory.lcs.mit.edu/clas...2/fall04/counting1.pdf
Anyone have any good ideas of going about it? Brute forcing is not an option as storing 10^27 values is not possible

 

[EvilYoda]

I'll have to read this in the morning.

You should tell him to post the problem on a chalkboard in the hallway so a genius janitor can solve it.

 

[KingNothing]

Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

Do you have to apply the same rule to each string? For instance, if you pick the first and third numbers from the first string, do you have to pick the first and third from all the other strings to form a subset?

One other question...say you have the number 123456, and you select the first and third digits. To create your sum, is the created term 1+3 = 4 or 13?

 

[Chronoshock]

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

How do you propose checking against 10^27 values?

 

[Evadman]

Originally posted by: Chronoshock

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

How do you propose checking against 10^27 values?

I can write a program that would do that in a short timeframe.

 

[DingDingDao]

Originally posted by: EvilYoda
I'll have to read this in the morning.

You should tell him to post the problem on a chalkboard in the hallway so a genius janitor can solve it.

:laugh:

Bookmarked for tomorrow morning. If nothing else, this looks like an interesting read...

 

[EmperorIQ]

Originally posted by: Evadman

Originally posted by: Chronoshock

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

How do you propose checking against 10^27 values?

I can write a program that would do that in a short timeframe.

ditto

 

[OulOat]

Why don't you brute force it, you got until the end of the final to turn in an answer.

 

[TheLonelyPhoenix]

I'm going to go ahead and declare this one impossible to do by computer. The algorithm has to be on the order of factorials.

 

[KingNothing]

How about some answers for my questions above?

 

[Chronoshock]

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

Do you have to apply the same rule to each string? For instance, if you pick the first and third numbers from the first string, do you have to pick the first and third from all the other strings to form a subset?

One other question...say you have the number 123456, and you select the first and third digits. To create your sum, is the created term 1+3 = 4 or 13?

I don't think you understand what you're supposed to be doing in this puzzle, you need to add each ENTIRE number to each other. Like 923843750874389573485 + 3987503987593845745 not just single digits. When I say number, I mean the entire number, not the components of the number. So you have to find a set of numbers in that list that adds up to the same total as another set of numbers in that list

 

[OulOat]

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

Do you have to apply the same rule to each string? For instance, if you pick the first and third numbers from the first string, do you have to pick the first and third from all the other strings to form a subset?

no, a subset is a smaller set of values belonging to larger set of values.

One other question...say you have the number 123456, and you select the first and third digits. To create your sum, is the created term 1+3 = 4 or 13?

This question makes no sense.

 

[Rogue]

I'm going to go ahead and keep an eye on this thread and see if people can put their money (or programming) where their mouth is. That said, I'm rooting for the programmers to solve the problem quickly.

 

[Evadman]

someone pull the numbers from that PDF and post em so I can try some stuff

 

[Chronoshock]

20480135385502964448038 3171004832173501394113017 5763257331083479647409398 8247331000042995311646021
489445991866915676240992 3208234421597368647019265 5800949123548989122628663 8496243997123475922766310
1082662032430379651370981 3437254656355157864869113 6042900801199280218026001 8518399140676002660747477
1178480894769706178994993 3574883393058653923711365 6116171789137737896701405 8543691283470191452333763
1253127351683239693851327 3644909946040480189969149 6144868973001582369723512 8675309258374137092461352
1301505129234077811069011 3790044132737084094417246 6247314593851169234746152 8694321112363996867296665
1311567111143866433882194 3870332127437971355322815 6814428944266874963488274 8772321203608477245851154
1470029452721203587686214 4080505804577801451363100 6870852945543886849147881 8791422161722582546341091
1578271047286257499433886 4167283461025702348124920 6914955508120950093732397 9062628024592126283973285
1638243921852176243192354 4235996831123777788211249 6949632451365987152423541 9137845566925526349897794
1763580219131985963102365 4670939445749439042111220 7128211143613619828415650 9153762966803189291934419
1826227795601842231029694 4815379351865384279613427 7173920083651862307925394 9270880194077636406984249
1843971862675102037201420 4837052948212922604442190 7215654874211755676220587 9324301480722103490379204
2396951193722134526177237 5106389423855018550671530 7256932847164391040233050 9436090832146695147140581
2781394568268599801096354 5142368192004769218069910 7332822657075235431620317 9475308159734538249013238
2796605196713610405408019 5181234096130144084041856 7426441829541573444964139 9492376623917486974923202
2931016394761975263190347 5198267398125617994391348 7632198126531809327186321 9511972558779880288252979
2933458058294405155197296 5317592940316231219758372 7712154432211912882310511 9602413424619187112552264
3075514410490975920315348 5384358126771794128356947 7858918664240262356610010 9631217114906129219461111
3111474985252793452860017 5439211712248901995423441 7898156786763212963178679 9908189853102753335981319
3145621587936120118438701 5610379826092838192760458 8147591017037573337848616 9913237476341764299813987
3148901255628881103198549 5632317555465228677676044 8149436716871371161932035
3157693105325111284321993 5692168374637019617423712 8176063831682536571306791

Enjoy

 

[bubbadu]

I am ALMOST crazy enough to try this tonight. All you would have to do is load everything into an array, then test every postion and if they match, output that into another array. I think I might give it a shot.

 

[Howard]

I'm not quite sure how I would approach this from coding perspective.

 

[chuckywang]

yeah, let's see it.

 

[Chronoshock]

Originally posted by: bubbadu
I am ALMOST crazy enough to try this tonight. All you would have to do is load everything into an array, then test every postion and if they match, output that into another array. I think I might give it a shot.

Yes this is the logical brute force method HOWEVER there are 2^90 subsets (ie the kth number is in the set or it isn't, thus the kth bit of a 90-bit string is either 0 or 1) resulting in a MASSIVE matrix that would fill up your entire harddrive. You have to use some sort of algorithm to reduce possibilities explored. One thing I've considered elminates it to ~10^26 subsets but that's still huge

 

[KingNothing]

Originally posted by: Chronoshock

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

Do you have to apply the same rule to each string? For instance, if you pick the first and third numbers from the first string, do you have to pick the first and third from all the other strings to form a subset?

One other question...say you have the number 123456, and you select the first and third digits. To create your sum, is the created term 1+3 = 4 or 13?

I don't think you understand what you're supposed to be doing in this puzzle, you need to add each ENTIRE number to each other. Like 923843750874389573485 + 3987503987593845745 not just single digits. When I say number, I mean the entire number, not the components of the number. So you have to find a set of numbers in that list that adds up to the same total as another set of numbers in that list

To quote the PDF: "For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column".

So it sounds like you can pull individual digits out of the number to create the sum for your subset. If I'm still misunderstanding, can you post the process for arriving at the answer? Doesn't matter if the numbers add up, just pretend they do.

 

[bubbadu]

Originally posted by: Chronoshock

Originally posted by: bubbadu
I am ALMOST crazy enough to try this tonight. All you would have to do is load everything into an array, then test every postion and if they match, output that into another array. I think I might give it a shot.

Yes this is the logical brute force method HOWEVER there are 2^90 subsets (ie the kth number is in the set or it isn't, thus the kth bit of a 90-bit string is either 0 or 1) resulting in a MASSIVE matrix that would fill up your entire harddrive. You have to use some sort of algorithm to reduce possibilities explored. One thing I've considered elminates it to ~10^26 subsets but that's still huge

What about some sort of BST or heap?

 

[Dubb]

n/m

 

[silverpig]

Originally posted by: EmperorIQ

Originally posted by: Evadman

Originally posted by: Chronoshock

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

How do you propose checking against 10^27 values?

I can write a program that would do that in a short timeframe.

ditto

Really? Even if you check 10 billion numbers per second you're still looking at 10^17 seconds.

 

[OulOat]

I say brute force it, but there is one smart way to do it. Instead of trying with 25 digit numbers, do it with the last digit of each number. I THINK a computer should be able to handle that. If not, you should have the computer resources at MIT to do it. Then partition the subsets according to the last digit of the sums. So you have all the subsets that the last digit of the sum is 0, 1, 2 etc. Then, within those subsets, you repeat the process with the last 2 digits, then the last 3 digits, etc etc. That should be easy to code and for the comp to handle. I hope I make sense.

 

[Chronoshock]

Originally posted by: KingNothing

Originally posted by: Chronoshock

Originally posted by: KingNothing
Brute forcing is too an option...you don't have to store all the possibilities, you just have to check all of them.

Do you have to apply the same rule to each string? For instance, if you pick the first and third numbers from the first string, do you have to pick the first and third from all the other strings to form a subset?

One other question...say you have the number 123456, and you select the first and third digits. To create your sum, is the created term 1+3 = 4 or 13?

I don't think you understand what you're supposed to be doing in this puzzle, you need to add each ENTIRE number to each other. Like 923843750874389573485 + 3987503987593845745 not just single digits. When I say number, I mean the entire number, not the components of the number. So you have to find a set of numbers in that list that adds up to the same total as another set of numbers in that list

To quote the PDF: "For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column".

So it sounds like you can pull individual digits out of the number to create the sum for your subset. If I'm still misunderstanding, can you post the process for arriving at the answer? Doesn't matter if the numbers add up, just pretend they do.

By first column, the prof is referring to the first of four columns of digits so say you have the numbers in the column of 20480135385502964448038 to 3157693105325111284321993 equal to the numbers in the column of 3171004832173501394113017 to 5692168374637019617423712