Chess Board Maths problem

Chess Board Maths problem

Posers and Puzzles

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.

Joined
26 Apr 03
Moves
26771
25 Feb 10

Originally posted by Campaigner
Right it's quite simple what I want, if I have an recognisible image of myself and the image is 100 pixels by 100 pixels, how many other images are there of similar similar resolution? Okay we've answered that; it's 2^10000, now can we store them all (at any memory size)? We've answered that; apparently not.
But we can store the sum total of their numeric values - can't we?
We can even work the value of that out.

Joined
26 Apr 03
Moves
26771
26 Feb 10

The sum of all the numbers representable with n bits, is:
2^(2n - 1) - 2^(n-1)

which, in the case of n=10000, can be written, in binary, as 10000 "1"s followed by 9999 "0"s

Joined
06 Apr 08
Moves
88278
27 Feb 10

...So is this number so big that it's impossble to 'work' with?

Joined
26 Apr 03
Moves
26771
27 Feb 10

Well, it's large, but not *that* large. You could probably do precise integer maths with it in various computing languages including Perl (with the BigInt module). You couldn't do maths with it very quickly at-all though, precise floating point maths would be very tricky and you would have no chance declaring an array with that many items.

I don't know why you would really want to though.

Joined
26 Apr 03
Moves
26771
27 Feb 10
6 edits

The number in question is:
99013842016898329617715360309560
12268523863902462129693567134328
26193179874650285213380048749877
97755418230568752456351415700188
46765957181087673520791351299060
76412134467491124133079888537977
69733480509794349863386139865970
65759909139363201742641060008228
30639651953551990914899676638590
08436892410674758203057491458345
93368093768501227293607039691363
87412814120962196189007943489070
84260169325045454848767983262516
37852471514322974148867868679901
02252949636591828315383595684670
66296563380953348001885192652642
28516555984550076329217386100619
31909408897127746054258482291269
71789278849536077319827815396941
97098068948592342055690209436512
94519195518348130434872340753278
55240420796232827605902628931503
90583844441977750876836587905672
43283762570793007220258225773327
57194215809521198053358377881169
36409173068492732446198645221377
80794109118893645965557267229221
08489547717522889072285689477326
06119803080757382127012537292861
44469999377458125074730069196704
45663030466950518124999619318913
78888733332240486701693080971018
19682325893654596168365571222819
57529219498312917056066483999247
78812466023143587388850608277194
35781279291793924261675302874409
38276012842852411884039355409475
93037068971462105542782248698871
02069051867572922520034481963379
27498933435409282103619541937162
47693563818785805075328757660287
36819818703749337573413098783877
67253503435742943906201463869113
78831764208712349427039298762001
02406334265380635861140121652807
75060091004388799115271016851231
70415833556044308463046700340289
99322993181555898938883693044961
73031531549829824139831939087037
39358961858487647852320229226265
06920766791720279541098479274260
92605369880730275798329105506579
95770478307271340486877520878911
42329179154451472487677315560407
68836332028445812172889655762280
00999215772807106314144924336417
25023839367498763417357047936837
25296651196153954002295322377006
26855666024680084106685465911132
37445402658220076606955786935891
16077063414003880156858436121104
80710048376109023785809998684473
38570052023369807270732330229276
16108598343832571573806099575960
63871615485023016071519076669262
29387156652667397380761696822517
18161459832815521164370231806282
92128020597351008700325394669813
80519172181165704575126955071930
59600588231329778194171529300163
35530945184187325828851060713846
66445895105299784629748589780204
28989582957085485028106434966796
79463431307599833829718540044254
65241153435764016066273677973708
99538019726528636159942161170941
62051819130879920094471956515093
84877493408680871078556435267235
06855798002287401781350694123411
25519576120953066033187046066087
71720833724497940803246459117679
91693012952471020362290508807984
21478850790404518048427202960229
71000346523062086831993884157661
32798112357875150896103862803966
26727184687938613100519368021778
38176163591717103398465286800020
36839746504472906980506219787198
68658931802731410382376033759721
01221355181718646594292154357309
89433482386181028645288663040332
23156482879512492987427205066692
10463568265483280331334137230395
72795098322321708701861610042848
09138434518221272166038115665106
78690060567233406040547392526043
42287354756879175515614504951285
85458690927477687611366065712705
95987341462269811881962815136762
35415378827589851292248437185552
46936112495225447586967848045174
71083350808316429137394064005284
54780417040759872574626601834808
43145400722598878479004312165355
93018665118677568041566425746989
15443521041338442270473175495846
50673662810169590218832197914024
00963538685765755676685490428239
10306008445404213117279762926446
05460249031425484286715423462781
24538091255392154072072410604456
67951961751635201958926294344866
57698523506991834943663638371544
64050942615269655926261220042625
48531323801554322704839429222233
89849773265083274881670086631623
98948359241895477233074087234415
22736459453087047721234164326758
87445123857802751130397111289686
81229841077884597015426267752519
52602770344378929482272743919049
91394781265544268536331422639000
59863752632732996252548499947385
44099280366177745582114829330397
84583449510785506810926861988635
77196807081352843100623288991683
96799399434115465783480406349662
76739149868150732957022370119874
57356707763626183620676427163582
08362521989061467210313261234366
02442882948091202772568632784953
78555885912369830241493074638574
15622737670032442697616098886107
08773681883705090377520117370760
02547213280114433332941181616357
75753695421187005277169618868498
69701536408870892427500083087660
25137301777399728417964616245939
26697839992012342203145812930882
70269634154763392898675099219125
94448666553651673046145264513919
00977497972042351796015973713836
36320345051601848105419803931793
12703055904107940107733468766785
90000167928285078889564247994413
51676134038841765716777875909519
64270141798147158705831806476182
89340232603056685414673885616087
96302611255921784551237445878088
89076356142592521564577626729921
24500554132449154929307094931689
01424009769401775608959211036423
07339104232309466052680882113912
47289177033531208647684054829590
25285096388480532577398756053867
77375133783250089951169949236925
70544713053528450342896608523632
03352988592977412098401152525504
98612482857936782385489269312554
40538708574336986077340392311769
34137506342718679927591507065315
14583766587465258859093314397013
40186520181540495661088274862606
88833942872349604445078647219954
48638392733846799717033758373672
94732932538625743025927181613147
63116901483807633702615337781183
21104505143806702361250857603962
82325328469100965628765041390721
14421051644854092926861832992575
08000267832146683794355357391896
03347426982302840223554373273937
87079779126428708703937517084645
16574319746536897277045201638624
45090924807008326811966256235769
80652803411856383631611390356741
41051551109302323398353402190166
47215972795244889173185904718317
42684612804774632161623259356172
97218628324912696558009330353791
61026231849771572506592931676079
40353527537685405360046667176166
25739394178170251969654346481698
91347629542156843199716384925535
01418672799430416918643381962483
54530339939789213897024953828198
81703420887692417649426196606130
72365459158958177655900843540480
0000

Joined
06 Apr 08
Moves
88278
28 Feb 10

Brilliant! Extremely Impressed.

Joined
06 Apr 08
Moves
88278
28 Feb 10

...even if it's not!

Joined
26 Apr 03
Moves
26771
28 Feb 10
1 edit

I think it's right. The perl program to produce the number was a bit shorter than the number, here it is:

use bigint;
print 2**(2*10000 - 1) - 2**(10000-1);

B

Joined
02 Mar 10
Moves
1162
02 Mar 10

There are two ways to answer such a question:

Suppose 100000000 and 000000001 are two 3x3 boards then:

1. If you are asked to count them as two different boards, then the correct answer is 2^(100x100) = 2^10000

2. If you are asked to count all symmetrically identical (identical by rotations and reflections) boards as a single board, then the correct answer is a bit more complicated and involves groups theory (Burnside's Lemma).

Joined
06 Apr 08
Moves
88278
19 Mar 10

Why should it involve a theory when you're going from all white squares to all black squares and everything in between. Imagine it like a chessboard, but all the files in one line of 1000 squares and instead of black have a 0 and instead of white having a 1, now doesn't that make it all easier? - or does it?

B

Joined
02 Mar 10
Moves
1162
28 Mar 10
1 edit

No, that does not make it any easier.
If you take symmetry into account, then you have much less options to count.
Not something you'd be willing to count by hand though.

Joined
06 Apr 08
Moves
88278
29 Mar 10

...thing is, I don't want to do anything spectacular with these numbers, just to create one for one instance then to recreate it in an other instance.

Joined
06 Apr 08
Moves
88278
10 Apr 10

How then to suit, if it was an actual chessboard? I am now going to create a 64 x 64 pixel image/photograph/picture. Now - how many other pictures like this are out there?