December 07, 2008

Taxman Game

Another gem from my neighbor Tom Sander. The "taxman" game is (apparently) an old programming exercise. But it is also a good game for practicing factors. I have been playing it a bit with Anthony (by hand). Here is a gadget that applies the rules of the game for you.

The rules are simple and fifth-grade friendly:

  • When you take a number, the taxman gets all the remaining factors.
  • You are only allowed moves that give the taxman at least one new number.
  • When you can't move any more, the taxman gets the rest.

It is worth playing without reading anything else - it is not too hard to find a heuristic that beats the taxman. The game was written up in an article by Moniot in the Feb 2007 MAA Horizons - an optimal strategy is not known.

I've gotten up to 121 points on the 20-size board; I am pretty sure this is not optimal. Can you beat the board with 100 squares? What is the best score you can get?

Posted by David at December 7, 2008 05:12 PM
Comments

David --

Highest I've been able to get to with board of 20 is 124 from drawing numbers in this order (19,14,10,20,16,15,12,18).

I suspect this is not optimal.

Best.

Tom

Posted by: Tom Sander at December 9, 2008 08:26 AM

Hm, I'm pretty sure 124 is optimal!

Posted by: David at December 11, 2008 09:22 PM

I got 2957 v 2093 using the "greedy" algorithm. I a fairly certain it isn't optimal.

John

Posted by: John Kemeny at January 5, 2009 04:09 PM

what's the highest possible score for Taxman 24?

Posted by: dude wheres my car? at November 4, 2009 06:57 PM

Im pretty sure the Highest possible score in Taxman is something like 1227. Thats the highest I've gotten with my friends soo... Yah...

Posted by: Dude What's mine say? at November 4, 2009 07:01 PM

isn't that..... impossible?

Posted by: dude wheres my car? at November 4, 2009 07:03 PM

hi

Posted by: at April 22, 2010 01:41 PM

I just got Score: 3006 Taxman: 2044

Posted by: dustin at July 13, 2010 05:46 PM

124 must be optimal. 19 is the correct first move as it is the largest prime on the board. Since 11, 13, and 17 are also prime and larger than half of 20, we cannot choose those, so the taxman gets them always. After the first move, there are 15 numbers that we can choose from left on the board, as 1, 11, 13, 17, and 19 are now gone. Since the taxman must receive at least one number each time we choose a number, the greatest number of picks that we have left is the floor of 15/2, which is 7. Thus we want 19 and the highest remaining 7 numbers, excluding 11, 13, and 17. The highest 7 remaining numbers would be, in descending order, 20, 18, 16, 15, 14, 12, 10. 19+20+18+16+15+14+12+10=124. Since there is a sequence of choices that will actually give us this outcome, that score is optimal.

Posted by: tony at April 2, 2011 12:28 PM

Did you know that you can type in 999 and it will make a board with 999 numbers. You can get scores over 25000

Posted by: will at April 12, 2011 08:46 AM

Impossible to win on 3 board.

Posted by: Bacon at January 11, 2012 09:26 AM

Yeah, 999 is hard. And yes, I knew that.

Posted by: Bacon at January 11, 2012 09:28 AM

Woo cares tony

Posted by: Rinder at February 20, 2012 09:46 AM

I'm not tony

Posted by: Bacon at May 16, 2012 09:46 AM

easy to beat 2 taxman hard on 500

Posted by: Ramsey at May 31, 2012 10:05 AM

hi

Posted by: ian at July 2, 2012 03:15 PM

love it!

Posted by: at July 31, 2012 11:12 AM

love this game

Posted by: arav at July 31, 2012 11:13 AM

First move should always be the largest prime number on the board.

Posted by: Pie Man at October 30, 2012 02:06 PM

Check here for scores taxman games up to n=50.

http://jeux.lulu.pagesperso-orange.fr/html/anglais/nbmyster/taxateur.htm

Alex (Germany)

Posted by: Alex at March 6, 2013 06:24 AM

The lowest number you can win at is 4

Posted by: STOP READING MY NAME at August 19, 2013 09:13 AM

Got 28403 on 947 board

Posted by: at April 1, 2014 04:02 PM

Whoooooot!!!!

Posted by: at April 1, 2014 04:02 PM

Hey guys I'm doing this for my assignment at uni. I'd done the greedy method and according to my mate, it's optimal. Basically taking the largest number each time with the smallest divisor (there's always a number with at 1 divisor). This display really helped me out as I slowly developed and tested this with this board.

For 100, I got 2970 - 2080

For 24, I got 178 - 122

For 947, I got 275607 - 173271

Mind telling me how you did it Mr.28403?

3 is a tie and actually the smallest number you can win with is 2.

Posted by: Butters at April 21, 2016 12:45 AM

http://www.nikevapor-max.us.com/
http://www.pandora-jewelry-charms.us.com/
http://www.nikeairmax270s.us.com/
http://www.fitflop-saleclearance.us.com/
http://www.disneypandoracharms.us/
http://www.isabel-marant.us.com/
http://www.airforce-1.us.com/
http://www.pandorajewelrycz.us.com/
http://www.balenciagaofficial.us.com/
http://www.adidashumanrace.us/
http://www.birkenstock-shoes.us/
http://www.jordan-4.us.com/
http://www.nikeairforce1.us.org/
http://www.nikeair-maxs.us.com/
http://www.vapormax-plus.us.com/
http://www.kyrieirving-shoes.us.org/
http://www.nikeshoes-cheap.us.com/
http://www.pandorashop.us.com/
http://www.edhardys.us.com/
http://www.fitflopsaleclearances.us.com/
http://www.ferragamo-outlets.us/
http://www.air-maxplus.us/
http://www.kyrie4.us.org/
http://www.monclersjackets.us.com/
http://www.pandoracharmsjewelrys.us.com/
http://www.ukair-max.org.uk/
http://www.valentinosshoes.us.org/
http://www.monclerjacket.us.org/
http://www.christian-louboutinsshoes.us.com/
http://www.jordan9.us.com/
http://www.nike-presto.us/
http://www.katespades-handbags.us.com/
http://www.skechers.us.com/
http://www.nmd-adidas.us.org/
http://www.pandorajewellery.us.com/
http://www.roshenike.us.com/
http://www.yeezys750.us/
http://www.kankenbackpacks.us/
http://www.fjallraven-kanken.us.com/
http://www.pandoracharms-clearance.us.com/
http://www.ferragamo-belts.us.com/
http://www.adidas-shoes.org.uk/
http://www.nikeoutletsonline.us.com/
http://www.pandoracharmsbracelets.us.com/
http://www.jordanshoesretro.us.com/
http://www.pandora-charmsoutlet.us.org/
http://www.katespadecom.us.com/
http://www.nikeclearances.us.com/
http://www.pandorascharm.us.org/
http://www.birkenstocks-outletonline.us.com/
http://www.pandorajewelrycharms.us.org/
http://www.airmax270.us.org/
http://www.jordan10.us.com/
http://www.burberryshandbags.us.com/
http://www.pandoras-jewelry.ca/
http://www.pandorajewelryofficial-site.us.com/
http://www.eccos.us.com/
http://www.balenciagatriples.us.org/
http://www.nikeairmax-shoes.us.com/
http://www.balenciagas.us.org/
http://www.shoeslouboutin.us.com/
http://www.canadapandoracharms.ca/
http://www.outletnikestore.us.com/
http://www.balenciagassneakers.us.com/
http://www.nikeairmaxs-270.us.com/
http://www.yeezysadidas.us.com/
http://www.jordanshoess.us.com/
http://www.retro-jordans.us/
http://www.nikeclearancestores.us.com/
http://www.pandoracharmsjewelry.us.org/
http://www.pandoraoutlet-charms.us.com/
http://www.pandoraringssite.us/
http://www.jordan-shoesformen.us.com/
http://www.airjordansneakers.us.com/
http://www.nike-airvapormaxflyknit.us/
http://www.nikesoutlet.us.com/
http://www.nike-sneakers.us.com/
http://www.christianlouboutin-outlets.us.com/
http://www.nikeairjordan.us.com/
http://www.pandorajewelrybracelets.us.com/
http://www.valentinooutletshoes.us.com/
http://www.pandora-online.us.com/
http://www.birkenstock-sandals.us.org/
http://www.christianlouboutin-heels.us.com/
http://www.pandoraofficialsite.us.com/
http://www.goyardsbags.us.com/
http://www.birkin-bag.us.com/
http://www.timberlands-outlet.us.com/
http://www.jordan11low.us.com/
http://www.birkenstocksandalsoutlet.us.com/
http://www.pandora-jewelryofficialsite.us.com/
http://www.yeezy-sneakers.us.com/
http://www.moncleroutlet-jackets.us.com/
http://www.pandora-bracelet.us.org/
http://www.nikeshoesforwomens.us/
http://www.newjordansshoes.us.com/
http://www.nike-basketballshoes.us/
http://www.pandorasjewelry.ca/
http://www.fitflop-shoes.us.org/
http://www.nikeoutletsfactory.us.com/
http://www.redbottomslouboutin.us.org/
http://www.katespades.us.org/
http://www.airmax270flyknit.us/
http://www.pandorabracelets.us.com/
http://www.pandoraonline.us/
http://www.pandorascharms.us.org/
http://www.louboutinshoes-uk.org.uk/
http://www.ralph-laurenukoutlet.org.uk/
http://www.christian-louboutinshoesuk.org.uk/
http://www.goyardshandbags.us.com/
http://www.yeezys-boost.us.org/
http://www.fitflop-outlet.us.com/
http://www.mbt-shoes.us.org/
http://www.adidas-stansmith.us.com/
http://www.pandoras-outlet.us.com/
http://www.monclerofficial.us.com/
http://www.jordans-sneakers.us.com/
http://www.superstarsadidas.us/
http://www.yeezy-700.us/
http://www.nmds.us.com/
http://www.longchampoutlet-online.us.com/
http://www.monclers.me.uk/
http://www.airjordan11s.us.com/
http://www.jordan-8.us/
http://www.nikeoutletsale.us.com/
http://www.ferragamos.us.org/
http://www.nikeairmax98.us/
http://www.jewelrypandora.us.org/
http://www.shoes-jordan.us.com/
http://www.pandorabracelet-clearance.us.com/
http://www.nikeshoes-formen.us/
http://www.sandalsfitflop.us.com/
http://www.bottegaveneta-handbags.us.com/
http://www.pandora-braceletcharms.us/
http://www.pandoracom.us/
http://www.pandoraoutletjewelry.us.org/
http://www.pandorajewelry-outlets.us.com/
http://www.pandorajewelry-officialsite.us.com/
http://www.outletbirkenstock.us.com/
http://www.adidasnmdr1.us.org/
http://www.airjordanretro11.us.com/
http://www.bottega-veneta.us.org/
http://www.vans-shoes.us/
http://www.nike-epicreact.us.com/
http://www.christianlouboutinsshoes.us.com/
http://www.nikefactory-store.us.com/
http://www.ecco-shoes.us.com/
http://www.curry5.us.org/
http://www.jordanretros.us.com/
http://www.nmdxr1.us/
http://www.jordan-12.us.com/
http://www.jordan11winlike96.us/
http://www.jordan14.us.com/
http://www.kate-spadeshandbags.us.com/
http://www.katespadeoutlets-online.us.com/
http://www.pandorajewelryofficial-site.us/
http://www.yeezyonline.us.com/
http://www.adidas-yeezy.org.uk/
http://www.superstaradidas.us.com/
http://www.redbottomshoeslouboutin.us.com/
http://www.adidasyeezysshoes.us.com/
http://www.nike-roshes.us/
http://www.pandoras.us.org/
http://www.airforceoneshoes.us.com/
http://www.pandorajewelrywebsite.us.com/
http://www.moncleroutletstoreonline.us.com/
http://www.pandoraa.us.com/
http://www.nikeoutletstoresonlineshopping.us.com/
http://www.yeezys-shoes.us.org/
http://www.fitflopsclearance.us.com/
http://www.nike-shoxs.us/

Posted by: Lisa at November 23, 2018 03:56 AM

http://www.nikeairmax270.org.uk/ air max 270
http://www.truereligion--jeans.us.com/ true religion hoodie
http://www.nikeairmax-90.us.com/ nike air vapormax
http://www.ralphlaurenspoloshirts.us.com/ polo ralph lauren
http://www.celines.us.com/ celine
http://www.airmax95.co.uk/ nike air max 95 mens
http://www.jordan11spacejams.us.com/ jordan retro 12
http://www.nikeairmax97.co.uk/ air max 97
http://www.jimmychooheels.us.com/ jimmy choo shoes
http://www.airmax270.co.uk/ air max 270
http://www.supreme--clothing.us.com/ supreme
http://www.pandora-jewelrysale.us.com/ pandora bracelet
http://www.jordans11shoes.us.com/ jordan 11
http://www.northfacejacketoutlets.us.com/ north face
http://www.burberry--scarf.us.com/ burberry shirt
http://www.monclerjacket.org.uk/ moncler jacket womens
http://www.fitflop--shoes.us.com/ fitflop uk
http://www.adidas-yeezy-shoes.us.com/ Yeezy Shoes
http://www.adidasnmdrunnerr1.us.com/ yeezy boost 350
http://www.birkenstocksandalssale.us.com/ birkenstock sale
http://www.christianlouboutinredbottoms.us.com/ red bottom shoes
http://www.michael-kors-bags.us.com/ mk handbags
http://www.longchampbackpack.us.com/ longchamp bag
http://www.jordanretro11-shoes.us.com/ jordan retro
http://www.salomonshoes.co.uk/ salomon
http://www.monclerjacketmens.us.com/ moncler jacket womens
http://www.nike-airmax270.us.com/ nike air max 90
http://www.eccoshoesoutlets.us.com/ ecco
http://www.moncler--jacket.us.com/ moncler coat
http://www.huaraches.us.com/ huarache
http://www.rayban--glasses.us.com/ ray ban eyeglasses
http://www.coachbags-outlet.us.com/ coach purses
http://www.yeezyboost350--v2.us.com/ yeezy boost 350
http://www.pandorauk.us.com/ pandora charms
http://www.polo-ralph-lauren.org.uk/ polo
http://www.chromehearts-jewelry.us.com/ chrome hearts jewelry
http://www.goyardbackpack.us.com/ goyard wallet
http://www.airmax-2018.us.com/ air max
http://www.true--religion.us.com/ true religion jeans for women
http://www.katespade--outlet.us.com/ kate spade handbags
http://www.montblancs.us.com/ mont blanc outlet
http://www.salvatore-ferragamo.us.com/ ferragamo
http://www.adidasnmd-womens.us.com/ adidas nmd womens
http://www.nike--shoes.co.uk/ nike shoes
http://www.jordan11.co.uk/ air jordan
http://www.monclers.uk/ moncler jacket
http://www.salomon-boots.us.com/ salomon
http://www.james-hardenshoes.us.com/ james harden
http://www.pandorajewelryscharms.us.com/ pandora jewelry
http://www.adidasoriginalsultraboost.us.com/ ultra boost
http://www.kd10-shoes.us.com/ kd 9
http://www.lebron15-shoes.us.com/ lebron 14
http://www.airjordan11spacejam.us.com/ jordan 11
http://www.adidas-yeezyboost350.us.com/ yeezy boost 350
http://www.mcm--bags.us.com/ mcm wallet
http://www.supremeshirt.us.com/ supreme clothing
http://www.skechers--shoes.us.com/ skechers boots
http://www.chrome--hearts.us.com/ chrome hearts ring
http://www.balenciagas-sneakers.us.com/ balenciaga trainers
http://www.adidas-superstarshoes.us.com/ adidas
http://www.lacosteshirts.us.com/ lacoste polo shirts
http://www.goyardbag.us.com/ goyard wallet
http://www.under-armour-shoes.us.com/ stephen curry shoes
http://www.mcms.us.com/ mcm backpack
http://www.burberry-bags.us.com/ burberry scarf
http://www.barbourjackets.co.uk/ barbour outlet
http://www.ed-hardys.us.com/ ed hardy shirt
http://www.kyrie-4.us.com/ kyire 4
http://www.cartier-bracelet.us.com/ cartier jewelry
http://www.nikeair-max90.co.uk/ nike air max 95
http://www.polo-ralphlauren-outlet.us.com/ ralph lauren polo shirts
http://www.redbottom--shoes.us.com/ red bottom shoes
http://www.salomon--shoes.us.com/ Salomon Speedcross 3
http://www.michaelkors-handbagss.us.com/ michael kors outlet
http://www.coach--bags.us.com/ coach purses
http://www.asicss.us.com/ asics womens running shoes
http://www.longchampbag.us.com/ longchamp le pliage
http://www.birkenstock--sandals.us.com/ birkenstock sale
http://www.balenciaga--shoes.us.com/ balenciaga bag
http://www.jordan--11.us.com/ jordan 11
http://www.moncler-coat.us.com/ moncler jacket
http://www.nikekdshoes.us.com/ nike kd
http://www.air-max-270.us.com/ nike air max 270
http://www.yeezyboost350shoes.us.com/ yeezy shoes
http://www.prada--bags.us.com/ prada bags
http://www.mbts.us.com/ mbt shoes
http://www.burberrys.org.uk/ burberry
http://www.stephen-curry-shoes.us.com/ curry 4 shoes
http://www.katespadepurses.us.com/ kate spade
http://www.pumarihannafenty.us.com/ fenty puma shoes
http://www.pandora--jewelrys.us.com/ pandora charms
http://www.hermes--belt.us.com/ hermes
http://www.kevin-durant-shoes.us.com/ kd 11
http://www.redbottoms-louboutin.us.com/ red bottoms
http://www.pandora-charmsjewelry.us.com/ pandora rings
http://www.air-max-97.us.com/ nike air max 97
http://www.air-max-90.us.com/ air max 90
http://www.prada--handbags.us.com/ prada wallet
http://www.louboutinredbottoms.us.com/ louboutin
http://www.kyrie-irving-shoes.us.com/ kyrie irving shoes
http://www.fitflop--sandals.us.com/ fitflop sale
http://www.pandora-jewelrybracelet.us.com/ pandora bracelet
http://www.katespadebags.us.com/ kate spade wallet
http://www.nikeairvapormaxflyknit.us.com/ nike air max
http://www.chromeheartsjewelrys.us.com/ chrome hearts t shirt
http://www.pandora--rings.us.com/ Pandora Rings
http://www.ferragamoshoess.us.com/ ferragamo shoes
http://www.nike-huaraches.us.com/ huarache shoes
http://www.nike--vapormax.us.com/ nike air vapormax
http://www.bvlgaris.us.com/ bulgari jewelry
http://www.pandorajewelryrings.us.com/ pandora bracelet
http://www.airmax90shoes.us.com/ nike vapormax
http://www.fitflopsshoes.us.com/ fitflop sandals
http://www.adidasyeezy-350.us.com/ yeezy
http://www.nikelebron15.us.com/ lebron shoes
http://www.vapormaxs.us.com/ nike vapor max
http://www.oakley--glasses.us.com/ oakley glasses
http://www.pandoraearrings.us.com/ pandora charms
http://www.ultra--boost.us.com/ ultra boost mens
http://www.nikeairmax-95.us.com/ nike air max 95 mens
http://www.adidas-ultraboost.us.com/ adidas ultra uncaged
http://www.ray--bansunglassess.us.com/ ray ban eyeglasses
http://www.air-max-95.us.com/ nike air max 95
http://www.hermesbirkin-handbags.us.com/ Hermes Handbags
http://www.salomonspeedcross3.us.com/ salomon speedcross 4
http://www.monclerjacketwomens.us.com/ moncler jacket mens
http://www.mulberry-handbags.us.com/ mulberry bag
http://www.adidasoriginalsnmd.us.com/ adidas originals nmd
http://www.asics--shoes.us.com/ asics shoes
http://www.nikeairmax-97.us.com/ air max 97 silver bullet
http://www.northface-jacket.us.com/ north face coats
http://www.valentino--shoes.us.com/ valentino shoes
http://www.fitflops-sale.us.com/ fitflop sale
http://www.pandoras-jewelrys.us.com/ pandora charms
http://www.ralphlauren--polo.us.com/ ralph lauren shirts
http://www.nike-airmax-2018.us.com/ nike air max
http://www.curry4-shoes.us.com/ under armour stephen curry
haohon23

Posted by: harden vol 1 at January 16, 2019 07:36 PM
Post a comment









Remember personal info?